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Ā
1
Ā andĀ100
Ā nodes.
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) |