This approach involves recursively checking each node of the trees. You start at the roots and compare their values. If they are the same, you proceed to check their left and right subtrees. If at any point the checks fail (either structure or node values don't match), you conclude that the trees are not identical.
The time complexity of this approach is O(N), where N is the total number of nodes in the trees, since each node is visited once. The space complexity is O(H) for the recursion stack, where H is the height of the trees.
1#include <iostream>
2using namespace std;
3struct TreeNode { int val; TreeNode *left; TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) {} };
4bool isSameTree(TreeNode* p, TreeNode* q) {
5 if (!p && !q) return true;
6 if (!p || !q) return false;
7 return (p->val == q->val) && isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
8}The solution in C++ is similar to C. We define a struct for the TreeNode and use a recursive function isSameTree that checks if two trees are identical by comparing the root values and recursively checking the left and right subtrees.
This approach involves using a stack to iteratively check whether two trees are identical. You use a stack to simulate the recursive process, always working on node pairs from both trees. For every processed pair, check for value equality, then push their children into the stack to process afterwards (with left and right children being compared correspondingly).
The time complexity remains O(N) since each node is processed exactly once. Space complexity could also be up to O(H) for the stack usage, being the tree's height.
1using System.Collections.Generic;
2public class TreeNode {
3 public int val;
4 public TreeNode left;
5 public TreeNode right;
6 public TreeNode(int x) { val = x; }
7}
8public class Solution {
9 public bool IsSameTree(TreeNode p, TreeNode q) {
10 Stack<TreeNode> stackP = new Stack<TreeNode>();
11 Stack<TreeNode> stackQ = new Stack<TreeNode>();
12 stackP.Push(p);
13 stackQ.Push(q);
14 while (stackP.Count > 0 && stackQ.Count > 0) {
15 TreeNode nodeP = stackP.Pop();
16 TreeNode nodeQ = stackQ.Pop();
17 if (nodeP == null && nodeQ == null)
18 continue;
19 if (nodeP == null || nodeQ == null || nodeP.val != nodeQ.val)
20 return false;
21 stackP.Push(nodeP.right);
22 stackP.Push(nodeP.left);
23 stackQ.Push(nodeQ.right);
24 stackQ.Push(nodeQ.left);
25 }
26 return stackP.Count == 0 && stackQ.Count == 0;
27 }
28}The C# solution uses .NET's Stack class. Nodes from each tree are processed iteratively until both stacks are empty, indicating the trees structure and values match entirely.