树
深度优先搜索
二叉树
题目描述
给你一棵二叉树的 root
节点,请按照以下方式收集树的节点:
收集所有的叶子节点。
移除所有的叶子节点。
重复以上步骤,直到树为空。
示例 1:
输入: root = [1,2,3,4,5]
输出: [[4,5,3],[2],[1]]
解释:
[[3,5,4],[2],[1]] 和 [[3,4,5],[2],[1]] 也被视作正确答案,因为每一层返回元素的顺序不影响结果。
示例 2:
输入: root = [1]
输出: [[1]]
提示:
树中节点的数量在[1, 100]
范围内。
-100 <= Node.val <= 100
解法
方法一
Python3 Java C++ Go
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 # Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution :
def findLeaves ( self , root : TreeNode ) -> List [ List [ int ]]:
def dfs ( root , prev , t ):
if root is None :
return
if root . left is None and root . right is None :
t . append ( root . val )
if prev . left == root :
prev . left = None
else :
prev . right = None
dfs ( root . left , root , t )
dfs ( root . right , root , t )
res = []
prev = TreeNode ( left = root )
while prev . left :
t = []
dfs ( prev . left , prev , t )
res . append ( t )
return res
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 /**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public List < List < Integer >> findLeaves ( TreeNode root ) {
List < List < Integer >> res = new ArrayList <> ();
TreeNode prev = new TreeNode ( 0 , root , null );
while ( prev . left != null ) {
List < Integer > t = new ArrayList <> ();
dfs ( prev . left , prev , t );
res . add ( t );
}
return res ;
}
private void dfs ( TreeNode root , TreeNode prev , List < Integer > t ) {
if ( root == null ) {
return ;
}
if ( root . left == null && root . right == null ) {
t . add ( root . val );
if ( prev . left == root ) {
prev . left = null ;
} else {
prev . right = null ;
}
}
dfs ( root . left , root , t );
dfs ( root . right , root , t );
}
}
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 /**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public :
vector < vector < int >> findLeaves ( TreeNode * root ) {
vector < vector < int >> res ;
TreeNode * prev = new TreeNode ( 0 , root , nullptr );
while ( prev -> left ) {
vector < int > t ;
dfs ( prev -> left , prev , t );
res . push_back ( t );
}
return res ;
}
void dfs ( TreeNode * root , TreeNode * prev , vector < int >& t ) {
if ( ! root ) return ;
if ( ! root -> left && ! root -> right ) {
t . push_back ( root -> val );
if ( prev -> left == root )
prev -> left = nullptr ;
else
prev -> right = nullptr ;
}
dfs ( root -> left , root , t );
dfs ( root -> right , root , t );
}
};
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 /**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func findLeaves ( root * TreeNode ) [][] int {
prev := & TreeNode {
Val : 0 ,
Left : root ,
Right : nil ,
}
var res [][] int
for prev . Left != nil {
var t [] int
dfs ( prev . Left , prev , & t )
res = append ( res , t )
}
return res
}
func dfs ( root , prev * TreeNode , t * [] int ) {
if root == nil {
return
}
if root . Left == nil && root . Right == nil {
* t = append ( * t , root . Val )
if prev . Left == root {
prev . Left = nil
} else {
prev . Right = nil
}
}
dfs ( root . Left , root , t )
dfs ( root . Right , root , t )
}
GitHub