Table of Contents
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 to be same trees 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
Problem Source: leetcode.com
Java Solution
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
/** * 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; * } * } */ class Solution { public boolean isSameTree(TreeNode p, TreeNode q) { //if both nodes p and q are null return true if(p==null && q==null) return true; //if TreeNode p is null and TreeNode q is not null or vice versa, return false if(p==null || q==null) return false; //Check value of TreeNode p and TreeNode q and check left subtree and right subtree //recursively return p.val == q.val && isSameTree(p.left, q.left) && isSameTree(p.right, q.right); } } |
Python Solution
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
''' https://leetcode.com/problems/same-tree/ ''' # Definition for a binary tree node. # class TreeNode(object): # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution(object): def isSameTree(self, p, q): """ :type p: TreeNode :type q: TreeNode :rtype: bool """ if not (p or q): return True if not (p and q): return False return (p.val == q.val) and self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right) |