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.
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: false
Constraints:
The number of nodes in both trees is in the range [0, 100].
-104 <= Node.val <= 104
Solutions
Solution 1: DFS
We can use the DFS recursive method to solve this problem.
First, determine whether the root nodes of the two binary trees are the same. If both root nodes are null, then the two binary trees are the same. If only one of the root nodes is null, then the two binary trees are definitely different. If both root nodes are not null, then determine whether their values are the same. If they are not the same, then the two binary trees are definitely different. If they are the same, then determine whether the left subtrees of the two binary trees are the same and whether the right subtrees are the same. The two binary trees are the same only when all the above conditions are met.
The time complexity is $O(\min(m, n))$, and the space complexity is $O(\min(m, n))$. Here, $m$ and $n$ are the number of nodes in the two binary trees, respectively. The space complexity mainly depends on the number of layers of recursive calls, which will not exceed the number of nodes in the smaller binary tree.
1 2 3 4 5 6 7 8 910111213
# Definition for a binary tree node.# class TreeNode:# def __init__(self, val=0, left=None, right=None):# self.val = val# self.left = left# self.right = rightclassSolution:defisSameTree(self,p:Optional[TreeNode],q:Optional[TreeNode])->bool:ifp==q:returnTrueifpisNoneorqisNoneorp.val!=q.val:returnFalsereturnself.isSameTree(p.left,q.left)andself.isSameTree(p.right,q.right)
1 2 3 4 5 6 7 8 910111213141516171819202122
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */classSolution{publicbooleanisSameTree(TreeNodep,TreeNodeq){if(p==q)returntrue;if(p==null||q==null||p.val!=q.val)returnfalse;returnisSameTree(p.left,q.left)&&isSameTree(p.right,q.right);}}
/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */funcisSameTree(p*TreeNode,q*TreeNode)bool{ifp==q{returntrue}ifp==nil||q==nil||p.Val!=q.Val{returnfalse}returnisSameTree(p.Left,q.Left)&&isSameTree(p.Right,q.Right)}
/** * Definition for a binary tree node. * class TreeNode { * public $val = null; * public $left = null; * public $right = null; * function __construct($val = 0, $left = null, $right = null) { * $this->val = $val; * $this->left = $left; * $this->right = $right; * } * } */class Solution { /** * @param TreeNode $p * @param TreeNode $q * @return Boolean */ function isSameTree($p, $q) { if ($p == null && $q == null) { return true; } if ($p == null || $q == null) { return false; } if ($p->val != $q->val) { return false; } return $this->isSameTree($p->left, $q->left) && $this->isSameTree($p->right, $q->right); }}
Solution 2: BFS
We can also use the BFS iterative method to solve this problem.
First, add the root nodes of the two binary trees to two queues. Each time, take out one node from each of the two queues and perform the following comparison operations. If the values of the two nodes are not the same, then the structures of the two binary trees are definitely different. If the values of the two nodes are the same, then determine whether the child nodes of the two nodes are null. If only the left child node of one node is null, then the structures of the two binary trees are definitely different. If only the right child node of one node is null, then the structures of the two binary trees are definitely different. If the structures of the left and right child nodes are the same, then add the left and right child nodes of the two nodes to the two queues respectively. For the next iteration, take out one node from each of the two queues for comparison. When both queues are empty at the same time, it means that we have compared all the nodes, and the structures of the two binary trees are completely the same.
The time complexity is $O(\min(m, n))$, and the space complexity is $O(\min(m, n))$. Here, $m$ and $n$ are the number of nodes in the two binary trees, respectively. The space complexity mainly depends on the number of elements in the queue, which will not exceed the number of nodes in the smaller binary tree.
/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */funcisSameTree(p*TreeNode,q*TreeNode)bool{ifp==q{returntrue}ifp==nil||q==nil{returnfalse}q1:=[]*TreeNode{p}q2:=[]*TreeNode{q}forlen(q1)>0&&len(q2)>0{p,q=q1[0],q2[0]ifp.Val!=q.Val{returnfalse}q1,q2=q1[1:],q2[1:]la,ra:=p.Left,p.Rightlb,rb:=q.Left,q.Rightif(la!=nil&&lb==nil)||(lb!=nil&&la==nil){returnfalse}if(ra!=nil&&rb==nil)||(rb!=nil&&ra==nil){returnfalse}ifla!=nil{q1=append(q1,la)q2=append(q2,lb)}ifra!=nil{q1=append(q1,ra)q2=append(q2,rb)}}returntrue}