Problem
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.
Note:
- Both of the given trees will have between
1and100nodes.
Solution: Recursion
Time complexity: O(n1 + n2)
Space complexity: O(n1 + n2)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
// Author: Huahua // Running time: 0 ms class Solution { public: bool leafSimilar(TreeNode* root1, TreeNode* root2) { vector<int> leafs1; vector<int> leafs2; getLeafs(root1, leafs1); getLeafs(root2, leafs2); return leafs1 == leafs2; } private: void getLeafs(TreeNode* root, vector<int>& leafs) { if (root == nullptr) return; if (root->left == nullptr && root->right == nullptr) leafs.push_back(root->val); getLeafs(root->left, leafs); getLeafs(root->right, leafs); } }; |
Python
|
1 2 3 4 5 6 7 8 9 10 11 |
""" Author: Huahua Running time: 24 ms """ class Solution(object): def leafSimilar(self, root1, root2): def getLeafs(root): if not root: return [] if not root.left and not root.right: return [root.val] return getLeafs(root.left) + getLeafs(root.right) return getLeafs(root1) == getLeafs(root2) |
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Paypal
Venmo
huahualeetcode
huahualeetcode
微信打赏
Be First to Comment