Same Tree
Given the roots of two binary trees, write a function to check if they are the same or not. Two binary trees are considered the same if they are structurally identical and the nodes have the same value.
Constraints:
- Both trees have at most 100 nodes.
- Both trees have values in the range [0, 100].
- Both trees do not have duplicate values.
Examples:
Input: [1,2,3], [1,2,3]
Output: true
Explanation: The two trees are the same because they have the same structure and node values.
Input: [1,2], [1,null,2]
Output: false
Explanation: The two trees are not the same because they have different structures.
Input: [1,2,1], [1,1,2]
Output: false
Explanation: The two trees are not the same because they have different node values.
Solutions
Recursive Approach
This solution uses a recursive approach to check if the two trees are the same. It checks if both trees are null, if one of them is null, or if the values of the nodes are different. If none of these conditions are met, it recursively checks the left and right subtrees.
class Solution:
def isSameTree(self, p:
TreeNode, q:
TreeNode) -> bool:
if not p and not q:
return True if not p or not q:
return False if p.val != q.val:
return False return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)Iterative Approach
This solution uses an iterative approach to check if the two trees are the same. It uses a stack to store the nodes to be compared. It checks if both trees are null, if one of them is null, or if the values of the nodes are different. If none of these conditions are met, it pushes the left and right subtrees into the stack.
var isSameTree = function (p, q) {
let stack = [[p, q]];
while (stack.length) {
let [node1, node2] = stack.pop();
if (!node1 && !node2) continue;
if (!node1 || !node2) return false;
if (node1.val !== node2.val) return false;
stack.push([node1.left, node2.left]);
stack.push([node1.right, node2.right]);
}
return true;
};
Follow-up:
How would you solve this problem if the trees are very large and do not fit into memory?
