每天一题LeetCode【第52天】

T102. Binary Tree Level Order Traversal【Medium】

题目

给出一个二叉树，

给定一个二叉树，按顺序返回其节点的值。 （即从左到右，逐级返回）。

举个例子：

给出二叉树 [3,9,20,null,null,15,7]

    3
   / \
  9  20
    /  \
   15   7

返回：

[
  [3],
  [9,20],
  [15,7]
]

思路

一般来说思路就是用一个 BFS 添加就好了。但是哈哈发现一个用 DFS 的，恩，有想法。

差别在于 DFS 的时候标记一下 level ，按 level 添加就好。

代码

代码取自 Top Solution，稍作注释

public List<List<Integer>> levelOrder(TreeNode root) {
        //创建返回类型
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        levelHelper(res, root, 0);
        return res;
    }
    
    public void levelHelper(List<List<Integer>> res, TreeNode root, int height) {
        //若是null就返回
        if (root == null) return;
        //根据深度增加动态添加一个ArrayList
        if (height >= res.size()) {
            res.add(new ArrayList<Integer>());
        }
        //根据深度添加val
        res.get(height).add(root.val);
        //增加深度遍历左右节点
        levelHelper(res, root.left, height+1);
        levelHelper(res, root.right, height+1);
    }