Question

Formatted question description: https://leetcode.ca/all/366.html

 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:

 1


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

 []

 @tag-tree

Algorithm

Each node is separated from the left child node and the right child node to get two depths,

Since the condition of becoming a leaf node is that the left and right child nodes are empty, we take the larger value of the left and right child nodes plus 1 as the depth value of the current node.

Knowing the depth value, you can add the node value to the correct position in the result.

Code

Java

  • import java.util.ArrayList;
    import java.util.List;
    
    public class Find_Leaves_of_Binary_Tree {
    
        public List<List<Integer>> findLeaves(TreeNode root) {
            List<List<Integer>> result = new ArrayList<List<Integer>>();
            helper(result, root);
            return result;
        }
    
        // traverse the tree bottom-up recursively
        private int helper(List<List<Integer>> list, TreeNode root) {
            if (root == null) {
                return -1; // @note: +1==0, mapping to list index
            }
    
            int left = helper(list, root.left);
            int right = helper(list, root.right);
            int currentDepthFromBottom = 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() <= currentDepthFromBottom) {
                list.add(new ArrayList<Integer>());
            }
    
            list.get(currentDepthFromBottom).add(root.val);
    
            return currentDepthFromBottom;
        }
    }
    
  • // OJ: https://leetcode.com/problems/find-leaves-of-binary-tree/
    // Time: O(N)
    // Space: O(H)
    class Solution {
    private:
        bool dfs(TreeNode *root, vector<int> &v) {
            if (!root) return true;
            if (!root->left && !root->right) {
                v.push_back(root->val);
                return true;
            }
            if (dfs(root->left, v)) root->left = NULL;
            if (dfs(root->right, v)) root->right = NULL;
            return false;
        }
        vector<int> removeLeaves(TreeNode *root) {
            vector<int> v;
            dfs(root, v);
            return v;
        }
    public:
        vector<vector<int>> findLeaves(TreeNode* root) {
            if (!root) return {};
            vector<vector<int>> ans;
            while (root->left || root->right) {
                ans.push_back(removeLeaves(root));
            }
            ans.push_back({ root->val });
            return ans;
        }
    };
    
  • # Definition for a binary tree node.
    # class TreeNode(object):
    #     def __init__(self, x):
    #         self.val = x
    #         self.left = None
    #         self.right = None
    import collections
    
    
    class Solution(object):
      def findLeaves(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """
    
        def helper(p, res):
          if not p:
            return 0
          left = helper(p.left, res)
          right = helper(p.right, res)
          depth = max(left, right) + 1
          res[depth].append(p.val)
          return depth
    
        ans = []
        res = collections.defaultdict(list)
        helper(root, res)
        for i in range(1, len(res) + 1):
          ans.append(res[i])
        return ans
    
    

All Problems

All Solutions