【题目】
请考虑一棵二叉树上所有的叶子,这些叶子的值按从左到右的顺序排列形成一个 叶值序列 。
举个例子,如上图所示,给定一颗叶值序列为 (6, 7, 4, 9, 8) 的树。
如果有两棵二叉树的叶值序列是相同,那么我们就认为它们是 叶相似 的。
如果给定的两个头结点分别为 root1 和 root2 的树是叶相似的,则返回 true;否则返回 false 。
提示:
给定的两棵树可能会有 1 到 100 个结点。
【思路】
主要有两个步骤:一是得到叶子节点序列,二是比较序列是否相同。
对于第一步,使用前序遍历/中序遍历,即可得到从左到右的叶子节点序列。
对于第二步,首先判断序列长度是否相同,接着判断元素是否相同。
【代码】
python版本
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def leafSimilar(self, root1, root2):
"""
:type root1: TreeNode
:type root2: TreeNode
:rtype: bool
"""
# 特殊情况,root为None
if not root1 and not root2:
return True
if (not root1 and root2) or (root1 and not root2):
return False
res1 = []
res2 = []
self.get_leaves(root1, res1)
self.get_leaves(root2, res2)
return res1 == res2
def get_leaves(self, node, res):
# 前序遍历,得到所有叶子节点
if not node.left and not node.right:
res.append(node.val)
if node.left:
self.get_leaves(node.left, res)
if node.right:
self.get_leaves(node.right, res)
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:
bool leafSimilar(TreeNode* root1, TreeNode* root2) {
if(!root1 && !root2)
return true;
if((!root1 && root2) || (root1 && !root2))
return false;
vector<int> res1;
vector<int> res2;
get_leaves(root1, res1);
get_leaves(root2, res2);
return is_equal(res1, res2);
}
void get_leaves(TreeNode* node, vector<int>& res){
// 前序遍历,得到所有叶子节点
if(!node->left && !node->right)
res.push_back(node->val);
if(node->left)
get_leaves(node->left, res);
if(node->right)
get_leaves(node->right, res);
}
bool is_equal(vector<int>& res1, vector<int>& res2){
// 判断两个vector是否相等
if(res1.size() != res2.size())
return false;
for(int i=0; i<res1.size(); i++)
if(res1[i] != res2[i])
return false;
return true;
}
};