java_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.

Examples

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].
• $-10^4$ <= Node.val <= $10^4$

解析

題目給出兩個二元樹的根結點要判斷兩個樹是否相同

兩顆樹相同的定義有兩個條件：

1. 結構相同
2. 每個相對應點的值相同

對於兩個二元樹的根結點 q, p 是相同可以歸納出以下檢驗條件

1. if q 是空值， p 必須是空值
2. if q 非空，p 必須非空， 且 p.Val = q.Val
3. q.Left 形成的子樹 與 p.Left 形成的子樹相同, q.Right 形成的子樹 與 p.Right 形成的子樹相同

程式碼

/**
 * 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 (p == null) {
      return q == null;
    }
    if (q != null) {
      if (p.val != q.val) {
        return false;
      }
      return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }
    return false;
  }
}

困難點

1. 理解兩個樹是相同的條件
2. 找出遞迴關係

Solve Point

• Understand what problem would like to solve
• Analysis Complexity