Given 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.
Input: [1, 2, 3], [1, 2, 3]
Output: true
Input: [1, 2], [1, null, 2]
Output: false
Input: [1, 2, 1], [1, 1, 2]
Output: false
Last updated
Was this helpful?
Was this helpful?
// 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;
}
}/**
* Time complexity : O(N), where N is a number of nodes in the tree, since one
* visits each node exactly once.
* Space complexity : O(log(N)) in the best case of completely balanced tree
* and O(N) in the worst case of completely unbalanced tree, to keep a
* recursion stack.
*/
class Solution {
public boolean isSameTree(TreeNode p, TreeNode q) {
if(p == null && q == null) {
return true;
}
if(p == null || q == null || p.val != q.val) {
return false;
}
return isSameTree(p.left, q.left) &&
isSameTree(p.right, q.right);
}
}/**
* Time complexity : O(N) since each node is visited exactly once.
* Space complexity : O(log(N)) in the best case of completely balanced tree
* and O(N) in the worst case of completely unbalanced tree, to keep a deque.
*/
class Solution {
public boolean isSameTree(TreeNode p, TreeNode q) {
if(p == null && q == null) return true;
if(p == null || q == null) return false;
Queue<TreeNode> pQueue = new LinkedList<TreeNode>();
Queue<TreeNode> qQueue = new LinkedList<TreeNode>();
pQueue.add(p);
qQueue.add(q);
while(!pQueue.isEmpty() && !qQueue.isEmpty()) {
TreeNode pTreeNode = pQueue.remove();
TreeNode qTreeNode = qQueue.remove();
if(pTreeNode.val != qTreeNode.val) return false;
if(pTreeNode.left != null && qTreeNode.left != null) {
pQueue.add(pTreeNode.left);
qQueue.add(qTreeNode.left);
} else if(pTreeNode.left != null || qTreeNode.left != null) {
return false;
}
if(pTreeNode.right != null && qTreeNode.right != null) {
pQueue.add(pTreeNode.right);
qQueue.add(qTreeNode.right);
} else if(pTreeNode.right != null || qTreeNode.right != null) {
return false;
}
}
return true;
}
}/**
* Time complexity : O(N) since each node is visited exactly once.
* Space complexity : O(log(N)) in the best case of completely balanced tree
* and O(N) in the worst case of completely unbalanced tree, to keep a deque.
*/
class Solution {
public boolean isSameTree(TreeNode p, TreeNode q) {
if(p == null && q == null) {
return true;
}
if(p == null || q == null) {
return false;
}
Queue<TreeNode> queue = new LinkedList();
queue.add(p);
queue.add(q);
while(!queue.isEmpty()) {
TreeNode n1 = queue.remove();
TreeNode n2 = queue.remove();
if(n1.val != n2.val) {
return false;
}
if(n1.left != null && n2.left != null) {
queue.add(n1.left);
queue.add(n2.left);
} else if(n1.left != null || n2.left != null) {
return false;
}
if(n1.right != null && n2.right != null) {
queue.add(n1.right);
queue.add(n2.right);
} else if(n1.right != null || n2.right != null) {
return false;
}
}
return true;
}
}