872. Leaf-Similar Trees 递归真的好用
Consider all the leaves of a binary tree. From left to right order, the values of those leaves form a leaf value sequence.
For example, in the given tree above, the leaf value sequence is (6, 7, 4, 9, 8)
.
Two binary trees are considered leaf-similar if their leaf value sequence is the same.
Return true
if and only if the two given trees with head nodes root1
and root2
are leaf-similar.
Constraints:
- Both of the given trees will have between
1
and200
nodes. - Both of the given trees will have values between
0
and200
之前对递归运用的不甚熟悉,最近算法刷多了自然就熟悉了,尤其对于树的便利。
这个题目,简单的保留前序过程中遇到的leaf就好,然后比较leaf列表。
class Solution {
public:
bool leafSimilar(TreeNode* root1, TreeNode* root2) {
vector<int> tree1;
vector<int> tree2;
visitTree(root1, tree1);
visitTree(root2, tree2);
if(tree1.size() != tree2.size())
return false;
if(tree1.size() == 0 and tree2.size() == 0)
return true;
for(int i = 0; i < tree1.size(); i++)
{
if(tree1[i] != tree2[i])
return false;
}
return true;
}
private:
void visitTree(TreeNode* root, vector<int>& res)
{
if(root == nullptr)
return;
if(root->left == nullptr and root->right == nullptr)
res.push_back(root->val);
visitTree(root->left, res);
visitTree(root->right, res);
}
};