The problem is straightforward and can be solved by creating two separate arrays, one containing leaves of the first tree and the other containing leaves of the second tree. We can create this array using simple DFS (make sure to recurse to the left subtree before the right subtree - this will give us the leaves strictly from left to right). Then we only have to compare these arrays. Alternatively, instead of using arrays, we can store the leaves in a string separated by some sentinel value like a “#”.
class Solution {
public:
bool leafSimilar(TreeNode* root1, TreeNode* root2) {
string t1, t2;
t1=t2="";
dfs(root1, t1);
dfs(root2, t2);
return t1==t2;
}
void dfs(TreeNode* root, string& s) {
if(root==NULL)
return;
if (root->left == NULL && root->right == NULL)
s+=to_string(root->val)+"#";
dfs(root->left, s);
dfs(root->right, s);
}
};
Time complexity: O(n) where n is the number of nodes in the tree
Space complexity: O(H) where H is the height of tree