请考虑一棵二叉树上所有的叶子，这些叶子的值按从左到右的顺序排列形成一个 叶值序列 。
举个例子，如上图所示，给定一棵叶值序列为 (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] 范围内
方法一：深度优先搜索
思路与算法
我们可以使用深度优先搜索的方法得到一棵树的「叶值序列」。
具体地，在深度优先搜索的过程中，我们总是先搜索当前节点的左子节点，再搜索当前节点的右子节点。如果我们搜索到一个叶节点，就将它的值放入序列中。
在得到了两棵树分别的「叶值序列」后，我们比较它们是否相等即可。
代码
[sol1-C++]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
| class Solution {
public:
void dfs(TreeNode* node, vector<int>& seq) {
if (!node->left && !node->right) {
seq.push_back(node->val);
}
else {
if (node->left) {
dfs(node->left, seq);
}
if (node->right) {
dfs(node->right, seq);
}
}
}
bool leafSimilar(TreeNode* root1, TreeNode* root2) {
vector<int> seq1;
if (root1) {
dfs(root1, seq1);
}
vector<int> seq2;
if (root2) {
dfs(root2, seq2);
}
return seq1 == seq2;
}
};
|
[sol1-Java]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
| class Solution {
public boolean leafSimilar(TreeNode root1, TreeNode root2) {
List<Integer> seq1 = new ArrayList<Integer>();
if (root1 != null) {
dfs(root1, seq1);
}
List<Integer> seq2 = new ArrayList<Integer>();
if (root2 != null) {
dfs(root2, seq2);
}
return seq1.equals(seq2);
}
public void dfs(TreeNode node, List<Integer> seq) {
if (node.left == null && node.right == null) {
seq.add(node.val);
} else {
if (node.left != null) {
dfs(node.left, seq);
}
if (node.right != null) {
dfs(node.right, seq);
}
}
}
}
|
[sol1-C#]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
| public class Solution {
public bool LeafSimilar(TreeNode root1, TreeNode root2) {
IList<int> seq1 = new List<int>();
if (root1 != null) {
DFS(root1, seq1);
}
IList<int> seq2 = new List<int>();
if (root2 != null) {
DFS(root2, seq2);
}
return seq1.SequenceEqual(seq2);
}
public void DFS(TreeNode node, IList<int> seq) {
if (node.left == null && node.right == null) {
seq.Add(node.val);
} else {
if (node.left != null) {
DFS(node.left, seq);
}
if (node.right != null) {
DFS(node.right, seq);
}
}
}
}
|
[sol1-Python3]1
2
3
4
5
6
7
8
9
10
11
12
13
14
| class Solution:
def leafSimilar(self, root1: TreeNode, root2: TreeNode) -> bool:
def dfs(node: TreeNode):
if not node.left and not node.right:
yield node.val
else:
if node.left:
yield from dfs(node.left)
if node.right:
yield from dfs(node.right)
seq1 = list(dfs(root1)) if root1 else list()
seq2 = list(dfs(root2)) if root2 else list()
return seq1 == seq2
|
[sol1-JavaScript]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
| var leafSimilar = function(root1, root2) {
const seq1 = [];
if (root1) {
dfs(root1, seq1);
}
const seq2 = [];
if (root2) {
dfs(root2, seq2);
}
return seq1.toString() === seq2.toString();
};
const dfs = (node, seq) => {
if (!node.left && !node.right) {
seq.push(node.val);
} else {
if (node.left) {
dfs(node.left, seq);
}
if (node.right) {
dfs(node.right, seq);
}
}
}
|
[sol1-Golang]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
| func leafSimilar(root1, root2 *TreeNode) bool {
vals := []int{}
var dfs func(*TreeNode)
dfs = func(node *TreeNode) {
if node == nil {
return
}
if node.Left == nil && node.Right == nil {
vals = append(vals, node.Val)
return
}
dfs(node.Left)
dfs(node.Right)
}
dfs(root1)
vals1 := append([]int(nil), vals...)
vals = []int{}
dfs(root2)
if len(vals) != len(vals1) {
return false
}
for i, v := range vals1 {
if v != vals[i] {
return false
}
}
return true
}
|
[sol1-C]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
| void dfs(struct TreeNode* node, int* seq, int* seqSize) {
if (!node->left && !node->right) {
seq[(*seqSize)++] = node->val;
} else {
if (node->left) {
dfs(node->left, seq, seqSize);
}
if (node->right) {
dfs(node->right, seq, seqSize);
}
}
}
bool leafSimilar(struct TreeNode* root1, struct TreeNode* root2) {
int seq1[200], seq1Size = 0;
if (root1) {
dfs(root1, seq1, &seq1Size);
}
int seq2[200], seq2Size = 0;
if (root2) {
dfs(root2, seq2, &seq2Size);
}
if (seq1Size != seq2Size) {
return false;
}
for (int i = 0; i < seq1Size; i++) {
if (seq1[i] != seq2[i]) {
return false;
}
}
return true;
}
|
复杂度分析
