10 lines simple Java solution using recursion with explanation | LeetCode Discuss

10 lines simple Java solution using recursion with explanation | LeetCode Discuss

public class Solution {      private List<List<Integer>> res = new ArrayList<>();      public List<List<Integer>> findLeaves(TreeNode root) {          helper(root);          return res;      }      private int helper(TreeNode node){          if(null==node)  return -1;          int height= 1 + Math.max(helper(node.left), helper(node.right));          if(res.size()<height+1)  res.add(new ArrayList<Integer>());          res.get(height).add(node.val);          // if need to actually remove the leaves, uncomment next line          // node.left = node.right = null;          return height;      }  }  

For this question we need to take bottom-up approach. The key is to find the height of each node. Here the definition of height is:
The height of a node is the number of edges from the node to the deepest leaf. --CMU 15-121 Binary Trees

I used a helper function to return the height of current node. According to the definition, the height of leaf is 0. h(node) = 1 + max(h(node.left), h(node.right)).
The height of a node is also the its index in the result list (res). For example, leaves, whose heights are 0, are stored in res[0]. Once we find the height of a node, we can put it directly into the result.

UPDATE:
Thanks @adrianliu0729 for pointing out that my previous code does not actually remove leaves. I added one line node.left = node.right = null; to remove visited nodes

UPDATE:
There seems to be some debate over whether we need to actually "remove" leaves from the input tree. Anyway, it is just a matter of one line code. In the actual interview, just confirm with the interviewer whether removal is required.

Read full article from 10 lines simple Java solution using recursion with explanation | LeetCode Discuss