366. Find Leaves of Binary Tree

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:

Input: [1,2,3,4,5]
  
          1
         / \
        2   3
       / \     
      4   5    

Output: [[4,5,3],[2],[1]]

Explanation:

1. Removing the leaves [4,5,3] would result in this tree:

          1
         / 
        2

2. Now removing the leaf [2] would result in this tree:

3. Now removing the leaf [1] would result in the empty tree:

[]

-----

Intuition

Need info from both left, and right child to determine if current node is leaf node

Post Order DFS

Consider looking up the tree from below where the level is determined as the height from below

Terminate recursion when node is null, return -1 so it can contribute to level 0

level = max(left, right) + 1

if level == ans.size()

ans.add(new ArrayList<Integer>())

ans.add(node.val)

node.left = node.right = null

return level

---

Time - O(N)

Space- O(N) - worst case, skewed tree

---

Related problems

104-maximum-depth-of-binary-tree

---

	/**
	* Definition of TreeNode:
	* public class TreeNode {
	* public int val;
	* public TreeNode left, right;
	* public TreeNode(int val) {
	* this.val = val;
	* this.left = this.right = null;
	* }
	* }
	*/


	public class Solution {
	/*
	* @param root: the root of binary tree
	* @return: collect and remove all leaves
	*/
	public List<List<Integer>> findLeaves(TreeNode root) {
	List<List<Integer>> ans = new ArrayList<List<Integer>>();
	if (root == null) {
	return ans;
	}

	postOrder(root, ans);
	return ans;
	}

	private int postOrder(TreeNode node, List<List<Integer>> ans) {
	if (node == null) {
	return -1;
	}

	int left = postOrder(node.left, ans);
	int right = postOrder(node.right, ans);

	int level = Math.max(left, right) + 1;

	if (level == ans.size()) {
	ans.add(new ArrayList<Integer>());
	}

	ans.get(level).add(node.val);
	node.left = null;
	node.right = null;

	return level;
	}
	}

SWE Interview preparation