leetcode解题: Find Leaves of Binary Tree (366)

发表于 | 分类于

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:
Given binary tree

1
2
3
4
5
6
7
8
9
10
          1
         / \
        2   3
       / \     
      4   5
```  
Returns [4, 5, 3], [2], [1].
Explanation:
1. Removing the leaves [4, 5, 3] would result in this tree:

  1
 /
2          

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
Returns [4, 5, 3], [2], [1].
### 解法1： DFS ###
这题一开始想用Hashtable把tree转化成一个图然后不停的拨洋葱，后来参考了别人的做法发现不需要这样。 每一个点属于第几层的leave是由他的高度决定的。 那么我们只要遍历一次，算出每一个node的高度，如果高度为0， 那么就是leaf， 放在结果的第一个vector中，如果高度为1，那么放在第二个vector中以此类推。
C++
{% codeblock lang:cpp %}
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    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 height = max(helper(root->left, res), helper(root->right, res)) + 1;
        if (height >= res.size()) res.resize(height + 1);
        res[height].push_back(root->val);
        return height;
    }
};
{% endcodeblock %}
Java
{% codeblock lang:java %}
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<List<Integer>> findLeaves(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if (root == null) {
            return res;
        }
        helper(root, res);
        return res;
    }
    private int helper(TreeNode root, List<List<Integer>> res) {
        if (root == null) {
            return -1;
        }
        int left = helper(root.left, res);
        int right = helper(root.right, res);
        int depth = Math.max(left, right) + 1;
        if (depth >= res.size()) {
            res.add(new ArrayList<Integer>());
        }
        res.get(depth).add(root.val);
        return depth;
    }
}
{% endcodeblock %}
### 解法2： 剥洋葱 ###
这种解法是用递归的方式不停的remove tree node。 用递归的方式的时候，如果要删掉一个leaf，办法是如果是leaf，则返回null， 而每一次递归的时候root->left = remove(left);
这样返回的NULL就会被赋值给root的left tree，所以就删掉了那个node。
每一次遍历的时候，都返回更新过的root， 直到root被删成空为止。
C++
{% codeblock lang: cpp %}
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> findLeaves(TreeNode* root) {
        vector<vector<int>> res;
        while (root) {
            vector<int> leaves;
            root = removeLeaves(root, leaves);
            res.push_back(leaves);
        }
        return res;
    }
    TreeNode* removeLeaves(TreeNode* root, vector<int>& leaves) {
        if (!root) {
            return NULL;
        }
        if (!root->left && !root->right) {
            leaves.push_back(root->val);
            return NULL;
        }
        root->left = removeLeaves(root->left, leaves);
        root->right = removeLeaves(root->right, leaves);
        return root;
    }
};
{% endcodeblock %}
```java
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<List<Integer>> findLeaves(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if (root == null) {
            return res;
        }
        while (root != null) {
            List<Integer> leaves = new ArrayList<>();
            root = remove(root, leaves);
            res.add(leaves);  
        }
        return res;        
    }
    private TreeNode remove(TreeNode root, List<Integer> leaves) {
        if (root == null) {
            return null;
        }
        if (root.left == null && root.right == null) {
            leaves.add(root.val);
            return null;
        }
        root.left = remove(root.left, leaves);
        root.right = remove(root.right, leaves);
        return root;
    }
}