树
深度优先搜索
二叉树
题目描述
请考虑一棵二叉树上所有的叶子,这些叶子的值按从左到右的顺序排列形成一个 叶值序列 。
举个例子,如上图所示,给定一棵叶值序列为 (6, 7, 4, 9, 8)
的树。
如果有两棵二叉树的叶值序列是相同,那么我们就认为它们是 叶相似 的。
如果给定的两个根结点分别为 root1
和 root2
的树是叶相似的,则返回 true
;否则返回 false
。
示例 1:
输入: root1 = [3,5,1,6,2,9,8,null,null,7,4], root2 = [3,5,1,6,7,4,2,null,null,null,null,null,null,9,8]
输出: true
示例 2:
输入: root1 = [1,2,3], root2 = [1,3,2]
输出: false
提示:
给定的两棵树结点数在 [1, 200]
范围内
给定的两棵树上的值在 [0, 200]
范围内
解法
方法一:DFS
后序遍历。
Python3 Java C++ Go Rust JavaScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15 # 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 leafSimilar ( self , root1 : Optional [ TreeNode ], root2 : Optional [ TreeNode ]) -> bool :
def dfs ( root ):
if root is None :
return []
ans = dfs ( root . left ) + dfs ( root . right )
return ans or [ root . val ]
return dfs ( root1 ) == dfs ( root2 )
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 /**
* 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 boolean leafSimilar ( TreeNode root1 , TreeNode root2 ) {
List < Integer > l1 = dfs ( root1 );
List < Integer > l2 = dfs ( root2 );
return l1 . equals ( l2 );
}
private List < Integer > dfs ( TreeNode root ) {
if ( root == null ) {
return new ArrayList <> ();
}
List < Integer > ans = dfs ( root . left );
ans . addAll ( dfs ( root . right ));
if ( ans . isEmpty ()) {
ans . add ( root . val );
}
return ans ;
}
}
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 /**
* 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 :
bool leafSimilar ( TreeNode * root1 , TreeNode * root2 ) {
return dfs ( root1 ) == dfs ( root2 );
}
vector < int > dfs ( TreeNode * root ) {
if ( ! root ) return {};
auto ans = dfs ( root -> left );
auto right = dfs ( root -> right );
ans . insert ( ans . end (), right . begin (), right . end ());
if ( ans . empty ()) ans . push_back ( root -> val );
return ans ;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23 /**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func leafSimilar ( root1 * TreeNode , root2 * TreeNode ) bool {
var dfs func ( * TreeNode ) [] int
dfs = func ( root * TreeNode ) [] int {
if root == nil {
return [] int {}
}
ans := dfs ( root . Left )
ans = append ( ans , dfs ( root . Right ) ... )
if len ( ans ) == 0 {
ans = append ( ans , root . Val )
}
return ans
}
return reflect . DeepEqual ( dfs ( root1 ), dfs ( root2 ))
}
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 // Definition for a binary tree node.
// #[derive(Debug, PartialEq, Eq)]
// pub struct TreeNode {
// pub val: i32,
// pub left: Option<Rc<RefCell<TreeNode>>>,
// pub right: Option<Rc<RefCell<TreeNode>>>,
// }
//
// impl TreeNode {
// #[inline]
// pub fn new(val: i32) -> Self {
// TreeNode {
// val,
// left: None,
// right: None
// }
// }
// }
use std :: rc :: Rc ;
use std :: cell :: RefCell ;
impl Solution {
#[allow(dead_code)]
pub fn leaf_similar (
root1 : Option < Rc < RefCell < TreeNode >>> ,
root2 : Option < Rc < RefCell < TreeNode >>>
) -> bool {
let mut one_vec : Vec < i32 > = Vec :: new ();
let mut two_vec : Vec < i32 > = Vec :: new ();
// Initialize the two vector
Self :: traverse ( & mut one_vec , root1 );
Self :: traverse ( & mut two_vec , root2 );
one_vec == two_vec
}
#[allow(dead_code)]
fn traverse ( v : & mut Vec < i32 > , root : Option < Rc < RefCell < TreeNode >>> ) {
if root . is_none () {
return ;
}
if Self :: is_leaf_node ( & root ) {
v . push ( root . as_ref (). unwrap (). borrow (). val );
}
let left = root . as_ref (). unwrap (). borrow (). left . clone ();
let right = root . as_ref (). unwrap (). borrow (). right . clone ();
Self :: traverse ( v , left );
Self :: traverse ( v , right );
}
#[allow(dead_code)]
fn is_leaf_node ( node : & Option < Rc < RefCell < TreeNode >>> ) -> bool {
node . as_ref (). unwrap (). borrow (). left . is_none () &&
node . as_ref (). unwrap (). borrow (). right . is_none ()
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15 var leafSimilar = function ( root1 , root2 ) {
const dfs = root => {
if ( ! root ) {
return [];
}
let ans = [... dfs ( root . left ), ... dfs ( root . right )];
if ( ! ans . length ) {
ans = [ root . val ];
}
return ans ;
};
const l1 = dfs ( root1 );
const l2 = dfs ( root2 );
return l1 . toString () === l2 . toString ();
};