Programming

Leetcode-100. Same Tree

By PattySung 10 July 2023
Leetcode-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:

image

Input: p = [1,2,3], q = [1,2,3]
Output: true

Example 2:

image

Input: p = [1,2], q = [1,null,2]
Output: false

Example 3:

image

Input: p = [1,2,1], q = [1,1,2]
Output: false

<解題>

  1. 如果兩者皆null，則相同true
  2. 只有任一null，則false
  3. p.val != q.val，則false
  4. return 判斷兩者左子樹與右子樹是否相同

class Solution {
   public boolean isSameTree(TreeNode p, TreeNode q) {
    
    // If both p and q are null, then they are the same tree
    if (p == null && q == null) return true;
    
    // If only one of p and q is null, then they are not the same tree
    if (p == null || q == null) return false;
    
    // If the values of p and q are different, then they are not the same tree
    if (p.val != q.val) return false;
    
    // Recursively check the left and right subtrees of p and q
    // If both the left and right subtrees are the same, then p and q are the same tree
    return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
  }
}