Question
Formatted question description: https://leetcode.ca/all/100.html
100 Same Tree
Given two binary trees, write a function to check if they are equal or not.
Two binary trees are considered equal if they are structurally identical and the nodes have the same value.
@tag-tree
Algorithm
Depth first search DFS to recurse.
Code
Java
public class Same_Tree {
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution_iteration {
public boolean isSameTree(TreeNode p, TreeNode q) {
if (p == null) {
return q == null;
}
if (q == null) {
return p == null;
}
Stack<TreeNode> sk1 = new Stack<TreeNode>();
Stack<TreeNode> sk2 = new Stack<TreeNode>();
sk1.push(p);
sk2.push(q);
while (!sk1.isEmpty() && !sk2.isEmpty()) {
TreeNode current1 = sk1.pop();
TreeNode current2 = sk2.pop();
if (current1 == null && current2 == null) {
continue; // @note: missed both null check
} else if (current1 == null && current2 != null) {
return false;
} else if (current1 != null && current2 == null) {
return false;
} else if (current1.val != current2.val) {
return false;
}
sk1.push(current1.left);
sk2.push(current2.left);
sk1.push(current1.right);
sk2.push(current2.right);
}
// final check
if (!sk1.isEmpty() || !sk2.isEmpty()) {
return false;
}
return true;
}
}
public class Solution_recursion {
public boolean isSameTree(TreeNode p, TreeNode q) {
if (p == null) {
return q == null;
}
if (q == null) {
return p == null;
}
if (p.val != q.val) {
return false;
}
return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
}
}
}