给你一个二叉树，请你返回其按 层序遍历 得到的节点值。 （即逐层地，从左到右访问所有节点）。
示例：二叉树：[3,9,20,null,null,15,7]
3 / \ 9 20 / \ 15 7
返回其层序遍历结果：
[ [3], [9,20], [15,7] ]
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/ class Solution { public List<List<Integer>> levelOrder(TreeNode root) { } }
解法
递归
相同层次的节点归入同一个数组 传入辅助的 level 参数决定层次
package com.javaedge.middle.tree; import java.util.ArrayList; import java.util.List; /**
* @author apple
*/ public class BinaryTreeLevelOrderTraversal { private static class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int x) { val = x; } } private static List<List<Integer>> levels = new ArrayList<>(); public static void helper(TreeNode node, int level) { // 假设将 root 作为第 0 层 if (levels.size() == level) { // 可得，此时需要新增该层级 levels.add(new ArrayList<>()); } // 对应层级的节点值list levels.get(level).add(node.val); // 递归遍历左子树 if (node.left != null) { helper(node.left, level + 1); } // 递归遍历右子树 if (node.right != null) { helper(node.right, level + 1); } } public static List<List<Integer>> levelOrder(TreeNode root) { if (root == null) { return levels; } helper(root, 0); return levels; } public static void main(String[] args) { TreeNode node1 = new TreeNode(3); TreeNode node2 = new TreeNode(9); TreeNode node3 = new TreeNode(20); TreeNode node4 = new TreeNode(15); TreeNode node5 = new TreeNode(7); node1.left = node2; node1.right = node3; node3.left = node4; node3.right = node5; System.out.println(levelOrder(node1)); } }
时间：O(N)，每个节点倍计算一次 空间：O(N)，输出包括 n 个节点
