# 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.

class Solution {
public:
bool leafSimilar(TreeNode* root1, TreeNode* root2) {
vector<int> leaf1, leaf2;
helper(root1, leaf1);
helper(root2, leaf2);
return leaf1 == leaf2;
}
void helper(TreeNode* node, vector<int>& leaf) {
if (!node) return;
if (!node->left && !node->right) {
leaf.push_back(node->val);
}
helper(node->left, leaf);
helper(node->right, leaf);
}
};

class Solution {
public:
bool leafSimilar(TreeNode* root1, TreeNode* root2) {
string leaf1, leaf2;
helper(root1, leaf1);
helper(root2, leaf2);
return leaf1 == leaf2;
}
void helper(TreeNode* node, string& leaf) {
if (!node) return;
if (!node->left && !node->right) {
leaf += to_string(node->val) + "-";
}
helper(node->left, leaf);
helper(node->right, leaf);
}
};

Github 同步地址:

https://github.com/grandyang/leetcode/issues/872

Binary Tree Preorder Traversal

https://leetcode.com/problems/leaf-similar-trees/

https://leetcode.com/problems/leaf-similar-trees/discuss/152329/C%2B%2BJavaPython-O(logN)-Space

https://leetcode.com/problems/leaf-similar-trees/discuss/152358/Simple-6-lines-Java-StringBuilder-%2B-traverse-with-explanation

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation