Description:
Given the roots of two binary trees p and q, 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.
Examples:
Example 1:
Input: p = [1,2,3], q = [1,2,3]
Output: true
Example 2:
Input: p = [1,2], q = [1,null,2]
Output: false
Example 3:
Input: p = [1,2,1], q = [1,1,2]
Output: falseSolution in Python:
Python
class Solution:
def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
# Base case: If both nodes are None, they are the same
if not p and not q:
return True
# If one of the nodes is None and the other is not, they are not the same
if not p or not q:
return False
# If the values of the current nodes are different, they are not the same
if p.val != q.val:
return False
# Recursively check the left and right subtrees
return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)Explanation of the Code
- TreeNode Definition:
- The
TreeNodeclass defines a binary tree node with a value (val) and optional left and right child nodes. - The constructor initializes these properties.
- The
- isSameTree Method:
- The
isSameTreemethod is the main function that checks if the two binary trees are the same.
- The
- Base Case:
- If both nodes
pandqareNone, they are considered the same (i.e., both trees are empty at this position), so returnTrue.
- If both nodes
- One Node is None:
- If one of the nodes is
Noneand the other is not, the trees are not the same, so returnFalse.
- If one of the nodes is
- Different Node Values:
- If the values of the current nodes
pandqare different, the trees are not the same, so returnFalse.
- If the values of the current nodes
- Recursive Check:
- Recursively check the left subtrees of
pandqusingself.isSameTree(p.left, q.left). - Recursively check the right subtrees of
pandqusingself.isSameTree(p.right, q.right). - Both recursive calls must return
Truefor the trees to be considered the same.
- Recursively check the left subtrees of
This solution ensures that we compare each corresponding node in both trees, ensuring they are structurally identical and have the same values.
Solution in Javascript:
JavaScript
/**
* @param {TreeNode} p
* @param {TreeNode} q
* @return {boolean}
*/
var isSameTree = function(p, q) {
// Base case: If both nodes are null, they are the same
if (!p && !q) {
return true;
}
// If one of the nodes is null and the other is not, they are not the same
if (!p || !q) {
return false;
}
// If the values of the current nodes are different, they are not the same
if (p.val !== q.val) {
return false;
}
// Recursively check left and right subtrees
return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
};Solution in Java:
Java
class Solution {
public boolean isSameTree(TreeNode p, TreeNode q) {
// Base case: If both nodes are null, they are the same
if (p == null && q == null) {
return true;
}
// If one of the nodes is null and the other is not, they are not the same
if (p == null || q == null) {
return false;
}
// If the values of the current nodes are different, they are not the same
if (p.val != q.val) {
return false;
}
// Recursively check left and right subtrees
return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
}
}Solution in C#:
C#
public class Solution {
public bool IsSameTree(TreeNode p, TreeNode q) {
// Base case: If both nodes are null, they are the same
if (p == null && q == null) {
return true;
}
// If one of the nodes is null and the other is not, they are not the same
if (p == null || q == null) {
return false;
}
// If the values of the current nodes are different, they are not the same
if (p.val != q.val) {
return false;
}
// Recursively check left and right subtrees
return IsSameTree(p.left, q.left) && IsSameTree(p.right, q.right);
}
}