Algorithm
Problem Nmae: 100. Same Tree
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
Code Examples
#1 Code Example with C Programming
Code -
C Programming
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
};
bool isSameTree(struct TreeNode *p, struct TreeNode *q) {
if (p == NULL && q == NULL)
return true;
else if (p && q) {
if (p->val == q->val
&& isSameTree(p->left, q->left)
&& isSameTree(p->right, q->right))
return true;
else return false;
}
else return false;
}
void printTreePreOrder(struct TreeNode *p) {
if (p != NULL) {
printf("%d", p->val);
printTreePreOrder(p->left);
printTreePreOrder(p->right);
}
else printf("#");
}
int main() {
struct TreeNode *t = (struct TreeNode *)calloc(3, sizeof(struct TreeNode));
struct TreeNode *p = t;
p->val = 1;
p->left = ++t;
t->val = 2;
t->left = t->right = NULL;
p->right = ++t;
t->val = 3;
t->left = t->right = NULL;
printTreePreOrder(p); printf("\n");
t = (struct TreeNode *)calloc(3, sizeof(struct TreeNode));
struct TreeNode *q = t;
q->val = 1;
q->left = ++t;
t->val = 2;
t->left = t->right = NULL;
q->right = ++t;
t->val = 4;
t->left = t->right = NULL;
printTreePreOrder(q); printf("\n");
printf("%d\n", isSameTree(p, q));
return 0;
}
Input
Output
#2 Code Example with C++ Programming
Code -
C++ Programming
class Solution {
public:
bool isSameTree(TreeNode* p, TreeNode* q) {
if (!p || !q) {
return !p && !q;
}
if (p->val != q->val) {
return false;
}
return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
}
};
Input
Output
#3 Code Example with Java Programming
Code -
Java Programming
class Solution {
public boolean isSameTree(TreeNode p, TreeNode q) {
if (p == null && q == null) {
return true;
}
if (p == null || q == null) {
return false;
}
if (p.val != q.val) {
return false;
}
return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
}
}
Input
Output
#4 Code Example with Javascript Programming
Code -
Javascript Programming
const isSameTree = function(p, 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)
};
Input
Output
#5 Code Example with Python Programming
Code -
Python Programming
class Solution:
def isSameTree(self, p, q):
return p == q if not p or not q else p.val == q.val and self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)
Input
Output
#6 Code Example with C# Programming
Code -
C# Programming
namespace LeetCode
{
public class _100_SameTree
{
public bool IsSameTree(TreeNode p, TreeNode q)
{
if (q == null && p == null) return true;
if (p == null || q == null) return false;
if (p.val != q.val) return false;
return IsSameTree(p.left, q.left) && IsSameTree(p.right, q.right);
}
}
}
Input
Output