## Saturday, June 25, 2016

### LeetCode 366 - Find Leaves of Binary Tree

http://www.cnblogs.com/grandyang/p/5616158.html
Given a binary tree, find all leaves and then remove those leaves. Then repeat the previous steps until the tree is empty.
Example:
Given binary tree
```          1
/ \
2   3
/ \
4   5
```
Returns `[4, 5, 3], [2], [1]`.

This problem does not actually ask you to remove leaves.
Originally, it did.
https://discuss.leetcode.com/topic/49194/10-lines-simple-java-solution-using-recursion-with-explanation
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.
``````    public List<List<Integer>> findLeaves(TreeNode root) {
List<List<Integer>> res = new ArrayList<>();
height(root, res);
return res;
}
private int height(TreeNode node, List<List<Integer>> res){
if(null==node)  return -1;
int level = 1 + Math.max(height(node.left, res), height(node.right, res));
return level;
}``````
Got almost exactly the same, but in Python. Only real difference is that my extension criterion is like `level == res.size()`, checking equality. I think the `<` makes it look like `res.size()` could actually be smaller than `level`, and I don't like giving that impression.
``````def findLeaves(self, root):
def dfs(node):
if not node:
return -1
i = 1 + max(dfs(node.left), dfs(node.right))
if i == len(out):
out.append([])
out[i].append(node.val)
return i
out = []
dfs(root)
return out``````
https://discuss.leetcode.com/topic/49206/java-backtracking-o-n-time-o-n-space-no-hashing
``````        public List<List<Integer>> findLeaves(TreeNode root) {
List<List<Integer>> list = new ArrayList<>();
findLeavesHelper(list, root);
return list;
}

// return the level of root
private int findLeavesHelper(List<List<Integer>> list, TreeNode root) {
if (root == null) {
return -1;
}
int leftLevel = findLeavesHelper(list, root.left);
int rightLevel = findLeavesHelper(list, root.right);
int level = Math.max(leftLevel, rightLevel) + 1;
if (list.size() == level) {
}
root.left = root.right = null;
return level;
}``````

```    vector<vector<int>> findLeaves(TreeNode* root) {
vector<vector<int>> res;
helper(root, res);
return res;
}
int helper(TreeNode *root, vector<vector<int>> &res) {
if (!root) return -1;
int depth = 1 + max(helper(root->left, res), helper(root->right, res));
if (depth >= res.size()) res.resize(depth + 1);
res[depth].push_back(root->val);
return depth;
}```
http://www.programcreek.com/2014/07/leetcode-find-leaves-of-binary-tree-java/
 ```public List> findLeaves(TreeNode root) { List> result = new ArrayList>(); helper(result, root); return result; }   // traverse the tree bottom-up recursively private int helper(List> list, TreeNode root){ if(root==null) return -1;   int left = helper(list, root.left); int right = helper(list, root.right); int curr = Math.max(left, right)+1;   // the first time this code is reached is when curr==0, //since the tree is bottom-up processed. if(list.size()<=curr){ list.add(new ArrayList()); }   list.get(curr).add(root.val);   return curr; }```

https://segmentfault.com/a/1190000005938045

``````if (list.size() == cur) {
}

``````    public List<List<Integer>> findLeaves(TreeNode root) {
List<List<Integer>> list = new ArrayList<>();
helper(list, root);
return list;
}

//calculate the index of this root passed in and put it in that index, at last return where this root was put
private int helper(List<List<Integer>> list, TreeNode root) {
if (root == null)
return -1;
int left = helper(list, root.left);
int right = helper(list, root.right);
int cur = Math.max(left, right) + 1;
if (list.size() == cur)
return cur;
}``````
https://leetcode.com/discuss/110389/12-lines-simple-java-solution-using-recursion
https://discuss.leetcode.com/topic/49206/java-backtracking-o-n-time-o-n-space-no-hashing
The essential of problem is not to find the leaves, but group leaves of same level together and also to cut the tree. This is the exact role backtracking plays. The helper function returns the level which is the distance from its furthest subtree leaf to root, which helps to identify which group the root belongs to
``````        public List<List<Integer>> findLeaves(TreeNode root) {
List<List<Integer>> list = new ArrayList<>();
findLeavesHelper(list, root);
return list;
}

// return the level of root
private int findLeavesHelper(List<List<Integer>> list, TreeNode root) {
if (root == null) {
return -1;
}
int leftLevel = findLeavesHelper(list, root.left);
int rightLevel = findLeavesHelper(list, root.right);
int level = Math.max(leftLevel, rightLevel) + 1;
if (list.size() == level) {
}
root.left = root.right = null;
return level;
}``````

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.

Only real difference is that my extension criterion is like `level == res.size()`, checking equality. I think the `<` makes it look like`res.size()` could actually be smaller than `level`, and I don't like giving that impression.
``````def findLeaves(self, root):
def dfs(node):
if not node:
return -1
i = 1 + max(dfs(node.left), dfs(node.right))
if i == len(out):
out.append([])
out[i].append(node.val)
return i
out = []
dfs(root)
return out``````
The essential of problem is not to find the leaves, but group leaves of same level together and also to cut the tree. This is the exact role backtracking plays. The helper function returns the level which is the distance from its furthest subtree leaf to root, which helps to identify which group the root belongs to
public List<List<Integer>> findLeaves(TreeNode root) { List<List<Integer>> list = new ArrayList<>(); findLeavesHelper(list, root); return list; } // return the level of root private int findLeavesHelper(List<List<Integer>> list, TreeNode root) { if (root == null) { return -1; } int leftLevel = findLeavesHelper(list, root.left); int rightLevel = findLeavesHelper(list, root.right); int level = Math.max(leftLevel, rightLevel) + 1; if (list.size() == level) { list.add(new ArrayList<>()); } list.get(level).add(root.val); root.left = root.right = null; return level; }
https://discuss.leetcode.com/topic/49663/simple-java-dfs-solution
`````` public List<List<Integer>> findLeaves(TreeNode root) {
List<List<Integer>> ans = new ArrayList<>();
dfs(root, ans);
return ans;
}
public int dfs(TreeNode root, List<List<Integer>> ans) {
if (root == null) {
return 0;
}
int up_cnt = Math.max(dfs(root.left, ans), dfs(root.right, ans));
while (ans.size() <= up_cnt) {
List<Integer> list = new ArrayList<>();
}
return up_cnt + 1;
}``````
X. https://leetcode.com/discuss/110406/simple-java-recursive-1ms-solution
This is pretty straight forward but the general idea is to simply prune the leaves at each iteration of the while loop until the root itself is pruned. We can do this using the x = change(x) paradigm for modifying a tree. Whenever we come across a leaf node, we know we must add it to our result but then we prune it by just returning null.
Clean solution. In worst cases, it can be O(N^2) right?
private TreeNode removeLeaves(TreeNode root, List<Integer> result) { if (root == null) return null; if (root.left == null && root.right == null) { result.add(root.val); return null; } root.left = removeLeaves(root.left, result); root.right = removeLeaves(root.right, result); return root; } public List<List<Integer>> findLeaves(TreeNode root) { List<List<Integer>> results = new ArrayList<List<Integer>>(); if (root == null) return results; while (root != null) { List<Integer> leaves = new ArrayList<Integer>(); root = removeLeaves(root, leaves); results.add(leaves); } return results; }
X.
https://discuss.leetcode.com/topic/49400/1-ms-easy-understand-java-solution
In worst case, this will be O(n^2)
``````    public List<List<Integer>> findLeaves(TreeNode root) {

List<List<Integer>> leavesList = new ArrayList< List<Integer>>();
List<Integer> leaves = new ArrayList<Integer>();

while(root != null) {
if(isLeave(root, leaves)) root = null;
leaves = new ArrayList<Integer>();
}
return leavesList;
}

public boolean isLeave(TreeNode node, List<Integer> leaves) {

if (node.left == null && node.right == null) {
return true;
}

if (node.left != null) {
if(isLeave(node.left, leaves))  node.left = null;
}

if (node.right != null) {
if(isLeave(node.right, leaves)) node.right = null;
}

return false;
}``````

```    vector<vector<int>> findLeaves(TreeNode* root) {
vector<vector<int>> res;
while (root) {
vector<int> leaves;
root = remove(root, leaves);
res.push_back(leaves);
}
return res;
}
TreeNode* remove(TreeNode *node, vector<int> &leaves) {
if (!node) return NULL;
if (!node->left && !node->right) {
leaves.push_back(node->val);
return NULL;
}
node->left = remove(node->left, leaves);
node->right = remove(node->right, leaves);
return node;
}
```
https://discuss.leetcode.com/topic/49205/java-use-map-straight
``````    public List<List<Integer>> findLeaves(TreeNode root) {
HashMap<Integer, List<Integer>> m = new HashMap<>();
int max = height(root, m);

for(int i = 1; i<max; i++){
if(m.containsKey(i))
}
return res;
}

public int height(TreeNode root, HashMap<Integer, List<Integer>> m){
if(root == null) return 0;
int max = Math.max(height(root.left, m), height(root.right, m)) + 1;
if(m.containsKey(max))
else{
m.put(max, l);
}
return max+1;
}``````
If you mean to make the root collectable, probably it will not happen as long as the caller still holds the reference ?