题目：
请考虑一棵二叉树上所有的叶子，这些叶子的值按从左到右的顺序排列形成一个 叶值序列 。
image.png
举个例子，如上图所示，给定一棵叶值序列为 (6, 7, 4, 9, 8) 的树。
如果有两棵二叉树的叶值序列是相同，那么我们就认为它们是 叶相似 的。
如果给定的两个头结点分别为 root1 和 root2 的树是叶相似的，则返回 true；否则返回 false 。
示例 1：
image.png
输入：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], root2 = [1]
输出：true
示例 3：
输入：root1 = [1], root2 = [2]
输出：false
示例 4：
输入：root1 = [1,2], root2 = [2,2]
输出：true
示例 5：
image.png
输入：root1 = [1,2,3], root2 = [1,3,2]
输出：false
提示：
给定的两棵树可能会有 1 到 200 个结点。
给定的两棵树上的值介于 0 到 200 之间。
链接：https://leetcode-cn.com/problems/leaf-similar-trees
思路：
1、遍历两个树，将2树的叶子结果保存起来进行对比
Python代码：
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution(object):
def __init__(self):
self.ret1 = []
self.ret2 = []
def dfs(self, root, ret):
if root.left==None and root.right==None:
ret.append(root.val)
return
if root.left:
self.dfs(root.left, ret)
if root.right:
self.dfs(root.right, ret)
return ret
def leafSimilar(self, root1, root2):
"""
:type root1: TreeNode
:type root2: TreeNode
:rtype: bool
"""
self.dfs(root1, self.ret1)
self.dfs(root2, self.ret2)
return self.ret1 == self.ret2
C++代码
/**
* 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:
void dfs(TreeNode* root, vector<int >& ret){
if (root==nullptr){
return;
}
if (root->left==NULL && root->right==NULL){
ret.push_back(root->val);
return;
}
dfs(root->left, ret);
dfs(root->right, ret);
}
bool leafSimilar(TreeNode* root1, TreeNode* root2) {
vector<int > ret1;
vector<int > ret2;
dfs(root1, ret1);
dfs(root2, ret2);
if (ret1.size()!=ret2.size()){
return false;
}
int size1 = ret1.size();
int size2 = ret2.size();
if (size1!=size2){
return false;
}
for (int i=0; i<size1; i++){
if (ret1[i]!=ret2[i]){
return false;
}
}
return true;
}
};
