LeetCode-BinaryTreeLevelOrderTraversal

发表于   |   更新于 | | 阅读数
字数统计 272 字 | 阅读时长 1 分钟

LeetCode-二叉树的按层遍历

思路：

  1. 如何确定同一层的节点？可以从根节点开始用0标记层数，然后累加，相同的层数表示在同一节点
  2. 使用容器或数组保存每一层的节点

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

public class BinaryTreeLevelOrderTraversal {

    public static 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;
        }
    }

    
    //按层输出，需要确定层数
    public static void getNodeLevel(TreeNode node,int level,List<List<Integer>> list){

        if(null == node){
            return;
        }else{
            if( level  > list.size()-1){
                list.add(level,new ArrayList<>());
            }
            list.get(level).add(node.val);
        }
        TreeNode left = node.left;
        TreeNode right = node.right;
        if(null != left || null != right){
            level++;
        }else{
            return;
        }
        getNodeLevel(left,level,list);
        getNodeLevel(right,level,list);
    }
    
}
  1. 递归代码中永远都需要小心确定循环的退出条件，空节点直接退出递归
  2. 当存在非空的子节点，将level累加向下传递
  3. 虽然没有按照 LeetCode 的代码提示方法去做，不过还是测试通过了