题目描述
考虑一棵二叉树从左到右的叶子的顺序,例如下图
则该树的叶子序列为(6, 7, 4, 9, 8)。
我们需要判断两棵二叉树的叶子序列是否相同,如果相同则返回true,否则返回false。
注意:树的节点树在1到100之间。
样例
输入:两棵二叉树的根节点root1, root2
输出:返回两棵树的叶子序列是否相同
算法
(先序遍历) $O(n)$
对两棵二叉树分别做先序遍历,同时判断每个节点是否是叶节点,如果是叶节点则加入到叶子序列中,然后再判断两棵树的叶子序列是否相同即可。
时间复杂度分析:需要遍历两棵树的节点,因此复杂度为$O(n)$。
C++ 代码
/**
* 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:
void getSequence(TreeNode* root, vector<int> &sequence){
if(!root)
return;
if(root->left){
getSequence(root->left, sequence);
}
if(root->right){
getSequence(root->right, sequence);
}
if(!root->left && !root->right){
sequence.push_back(root->val);
}
}
bool leafSimilar(TreeNode* root1, TreeNode* root2) {
vector<int>seq1,seq2;
getSequence(root1,seq1);
getSequence(root2,seq2);
if(seq1.size()!=seq2.size()){
return false;
}
for(int i = 0;i<seq1.size();i++){
if(seq1[i]!=seq2[i])
return false;
}
return true;
}
};