Sponsored
Sponsored
This approach involves using a recursive depth-first search (DFS) to traverse each binary tree and collect the leaf node values by diving into each sub-tree starting from the root node. We store the values of all leaf nodes from left to right in a list. After extracting the sequences from both trees, we compare these sequences to determine if the trees are leaf-similar.
Time Complexity: O(N) where N is the number of nodes in the tree, as we need to visit each node.
Space Complexity: O(H) where H is the height of the tree, due to the recursive stack.
1#include <vector>
2using namespace std;
3
4struct TreeNode {
5 int val;
6 TreeNode *left;
7 TreeNode *right;
8 TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
9};
10
11class Solution {
12public:
13 bool leafSimilar(TreeNode* root1, TreeNode* root2) {
14 vector<int> leaves1, leaves2;
15 dfs(root1, leaves1);
16 dfs(root2, leaves2);
17 return leaves1 == leaves2;
18 }
19
20private:
21 void dfs(TreeNode* node, vector<int>& leaves) {
22 if (!node) return;
23 if (!node->left && !node->right) {
24 leaves.push_back(node->val);
25 } else {
26 dfs(node->left, leaves);
27 dfs(node->right, leaves);
28 }
29 }
30};The solution uses a helper method called dfs that performs a depth-first search on each tree. If a node is a leaf node (no children), its value is appended to a leaves vector. The vectors of leaf nodes from the two trees are compared to ascertain leaf similarity.
This method employs an iterative version of depth-first search utilizing a stack to collect leaves of the tree. By substituting recursion with a stack, we manually handle tree traversal, but the core logic remains similar: traverse each tree, collect leaves, and compare leaf sequences.
Time Complexity: O(N), with N as the number of nodes in the tree, because every node is visited.
Space Complexity: O(H), where H is the height of the tree. This space is used by the stack during DFS traversal.
1function TreeNode(val, left, right)
This JavaScript implementation employs a stack in lieu of recursion, traversing the tree iteratively while storing leaf values in an array leaves. By iterating over the stack, we manage the state of traversal explicitly. Comparison between the leaf sequences relies on checking equality between the serialized JSON strings for simplicity.