LeetCode-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.
Note:
- Both of the given trees will have between
1
and100
nodes.
题解:
class Solution {
public:
static void dfs(TreeNode* p, vector<int> &res) {
if (p->left == NULL && p->right == NULL) {
res.push_back(p->val);
}
if (p->left != NULL) {
dfs(p->left, res);
}
if (p->right != NULL) {
dfs(p->right, res);
}
}
bool leafSimilar(TreeNode* root1, TreeNode* root2) {
vector<int> res1, res2;
dfs(root1, res1);
dfs(root2, res2);
int l1 = res1.size(), l2 = res2.size();
if (l1 != l2) {
return false;
}
else {
for (int i = 0; i < l1; i++) {
if (res1[i] != res2[i]) {
return false;
}
}
return true;
}
}
};