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