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.
1import java.util.Stack;
2
Here, a Stack is used for both implementing the DFS traversal and collecting leaf node values iteratively. For leaf nodes, their values are added to a separate stack (list) leaves. By performing this for both root1 and root2, we get their leaf sequences, which are compared for equality at the end.