366. Find Leaves of Binary Tree

Version #2 BFS 想到用topological sort的方法，空间复杂度比DFS高很多，就不考虑了

三刷 08/2022

Version #1 DFS

Time O(N) - number of nodes

Space O(N) - height of the tree

Runtime: 0 ms, faster than 100.00% of Java online submissions for Find Leaves of Binary Tree.

Memory Usage: 42.8 MB, less than 18.88% of Java online submissions for Find Leaves of Binary Tree.

class Solution {

    public List<List<Integer>> findLeaves(TreeNode root) {

        // add to result by height

        // height of a node is max(left height, right height) + 1

        List<List<Integer>> result = new ArrayList<>();

        dfs(root, result);

        return result;

    }

    

    private int dfs(TreeNode node, List<List<Integer>> result) {

        if (node == null) {

            return 0;

        }

        int h = 0;

        if (node.left != null || node.right != null) {

            h = 1 + Math.max(dfs(node.left, result), dfs(node.right, result));

        }

        if (result.size() == h) {

            result.add(new ArrayList<>());

        }

        result.get(h).add(node.val);

        return h;

    }

}

Version #1 DFS
二刷
34.30 %
class Solution {
    public List<List<Integer>> findLeaves(TreeNode root) {
        // 1 node's height is defined as 1 + min(leftHeight, rightHeight)
        List<List<Integer>> result = new ArrayList<>();
        dfs(root, result);
        return result;
    }
   
    private int dfs(TreeNode node, List<List<Integer>> result) {
        if (node == null) {
            return Integer.MIN_VALUE;
        }
        int height = 0;
        if (node.left == null && node.right == null) {
            height = 0;
        } else {
            height = 1 + Math.max(dfs(node.left, result), dfs(node.right, result));
        }
        if (result.size() <= height) {
            result.add(new ArrayList<>());
        }
        result.get(height).add(node.val);
        // System.out.println(node.val + " " + height);
        return height;
    }
}
一刷
Using the depth of each node to distinguish their index in the result list
The depth is defined by the depth of its deepest child subtree, plus 1.
Since we are adding the nodes to their corresponding lists while we are traversing the tree, each node is visited only once. So the time complexity is O(n)
Space cost is the system stack used by the recursive call. Even recursion call stopped when we reached the leaf of the tree. So the stack scale is the height of the tree O(h).
这个code应该把depth改成height

17.75 % 
class Solution {
    public List<List<Integer>> findLeaves(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) return result;
        //TODO
        findLeavesDFSHelper(root, result);
        return result;
    }
    // return the depth of the current node
    private int findLeavesDFSHelper(TreeNode root, List<List<Integer>> result) {
        if (root == null) return -1;
        int leftDepth = findLeavesDFSHelper(root.left, result);
        int rightDepth = findLeavesDFSHelper(root.right, result);
        int depth = Math.max(leftDepth, rightDepth) + 1;
        if (depth == result.size()) result.add(new ArrayList<Integer>());
        result.get(depth).add(root.val);
        return depth;
    }
}