LeetCode
comments powered by Disqus
Editorial: LeetCode 366 Find Leaves of Binary Tree
https://leetcode.com/problems/find-leaves-of-binary-tree/ from Google
Solutions:
1. DFS with sorting
Calculate the depth reversely. Leaves has depth 0. Their parents has depth 1 and so on. After we get all the depth, we sort them increasingly. Then, get the answer based on the sorted array.
1class Solution {
2public:
3 vector<pair<int, TreeNode*>> depthArray;
4 int dfs(TreeNode* n) {
5 if (n == NULL) return -1;
6 int left = dfs(n->left);
7 int right = dfs(n->right);
8 int depth = max(left, right) + 1;
9 depthArray.push_back({depth, n});
10 return depth;
11 }
12 vector<vector<int>> findLeaves(TreeNode* root) {
13 dfs(root);
14 sort(depthArray.begin(), depthArray.end());
15 vector<vector<int>> ans;
16 int N = depthArray.size();
17 int i = 0;
18 int d = 0;
19 while (i < N) {
20 vector<int> tmp;
21 while (i<N and depthArray[i].first == d) {
22 tmp.push_back(depthArray[i].second->val);
23 i++;
24 }
25 d++;
26 ans.push_back(tmp);
27 }
28 return ans;
29 }
30};
Time complexity: O(NlogN) because of sorting. Space complexity: O(N) even not considering the output.
2. DFS without sorting
We don’t need the sorting. We just need to insert the value of the node into the array according to its depth. For example, if the depth is 1 (calculated from the bottom), then the value must be inserted into the ans[1] array, so if the ans size is smaller than the depth, we push one more empty array to it.
1class Solution {
2public:
3 vector<vector<int>> ans;
4 int dfs(TreeNode* n) {
5 if (n == NULL) return -1;
6 int left = dfs(n->left);
7 int right = dfs(n->right);
8 int depth = max(left, right) + 1;
9 if (depth >= ans.size()) {
10 ans.push_back(vector<int>());
11 }
12 ans[depth].push_back(n->val);
13 return depth;
14 }
15 vector<vector<int>> findLeaves(TreeNode* root) {
16 dfs(root);
17 return ans;
18 }
19};
Time complexity: O(N). Space complexity: O(N).