366. Find Leaves of Binary Tree

Leetcode Tree Depth-first Search

Given a binary tree, collect a tree's nodes as if you were doing this: Collect and remove all leaves, repeat until the tree is empty.

Example

Given binary tree:

    1
   / \
  2   3
 / \     
4   5    
Returns [[4, 5, 3], [2], [1]].
Explanation:

1. Remove the leaves [4, 5, 3] from the tree
          1
         / 
        2          
2. Remove the leaf [2] from the tree
          1          
3. Remove the leaf [1] from the tree
          []         
Returns [4, 5, 3], [2], [1].

分析

寻找二叉树的叶子节点。可以从例子中观察得到，节点在结果中的位置下标，等于以该节点为根节点的二叉树的深度。所以一个最直接的思路是该节点为根节点的二叉树的深度，在相应位置添加节点的值。

public List<List<Integer>> findLeaves(TreeNode root) {
    int height = maxHeight(root);
    List<List<Integer>> list = new ArrayList<>();
    if (height == 0) return list;

    for (int i = 0; i < height; i++)
        list.add(new ArrayList<Integer>());
    list.get(height - 1).add(root.val);
    traversal(list, root.left);
    traversal(list, root.right);
    return list;
}

private int maxHeight(TreeNode root) {
    if (root == null) return 0;
    return 1 + Math.max(maxHeight(root.left), maxHeight(root.right));
}

private void traversal(List<List<Integer>> list, TreeNode root) {
    if (root == null) return;
    list.get(maxHeight(root) - 1).add(root.val);
    traversal(list, root.left);
    traversal(list, root.right);
}