366. Find Leaves of Binary Tree

https://leetcode.com/problems/find-leaves-of-binary-tree/description/

DFS with node Height

class Solution {
    public List<List<Integer>> findLeaves(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        dfsHeight(root, res);
        
        return res;
    }
    
    private int dfsHeight(TreeNode root, List<List<Integer>> res) {
        if (root == null) {
            return 0;
        }
        
        int leftChildDepth = dfsHeight(root.left, res);
        int rightChildDepth = dfsHeight(root.right, res);
        int depth = Math.max(leftChildDepth, rightChildDepth) + 1;
        
        if (res.size() < depth) {
            ArrayList<Integer> list = new ArrayList<>();
            res.add(list);
        }
        
        res.get(depth - 1).add(root.val);
        
        return depth;
    }
}

这道题目题解和199. Binary Tree Right Side View 很相似。巧妙的使用 list size 和 depth or height 的关系。

// 199. Binary Tree Right Side View 题解

class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> list = new LinkedList<>();
        dfsDepth(root, 0, list);
        
        return list;
    }
    
    private void dfsDepth(TreeNode root, int depth, List<Integer> list) {
        if (root == null) {
            return;
        }
        
        if (depth == list.size()) {
            list.add(root.val);
        }
        
        dfsDepth(root.right, depth + 1, list);
        dfsDepth(root.left, depth + 1, list);
    }
}

这里可以顺便比较 Tree Depth 和 Height Recursion 实现的区别。

• Height：自底向上，需要返回当前 node height，以便进行 parent height 运算；
• Depth：自顶向下，需要传递参数当前 node depth, 以便进行 child 相关运算。