100. Same Tree
Description
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.
Constraints
Approach
Links
Examples
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
Solutions
// 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;
}
}Follow up
Last updated
Was this helpful?