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:

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

效能

• Time complexity: O(n)
• Space complexity: O(n)
• Runtime: 101 ms
• Memory: 40 MB

遞迴比較

關於二元樹的 class 如下：

public class TreeNode { 
    public int val; 
    public TreeNode left; 
    public TreeNode right; 
    public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) { 
        this.val = val; 
        this.left = left; 
        this.right = right; 
    } 
}

首先來看最一開始拿到的兩個 TreeNode。如果他們兩個剛好都是 null，就代表我們剛好檢視完所有的值了，所以這兩棵樹是一樣的，回傳 true。如果一邊是 null 但另外一邊不是，就代表兩棵樹的高度不太一樣，所以會回傳 false。

0    0    ---> 相等的樹 
   0    n    ---> 不相等的樹

確定好兩邊的 TreeNode 都不是 null 後，再比較兩邊的值，如果不一樣就回傳 false。

0    1   ---> 不相等的樹

寫成程式碼會長這樣：

public bool 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; 
}

如果樹不只一層，比如說：

p    q 
   0    0 
  1 2  2 3

接下來就是要分別去比左邊 p = 1, q = 2 和右邊 p = 2, q = 3 的部分。要比的內容其實一樣，先看兩邊有沒有包含 null，都沒有的話就比值，值一樣就繼續往下比左邊和右邊。完整程式碼如下：

public bool 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; 
 
    var isSameTreeInLeft = IsSameTree(p.left, q.left); 
    var isSameTreeInRight = IsSameTree(p.right, q.right); 
     
    return isSameTreeInLeft && isSameTreeInRight; 
}

參考資料

• 100. Same Tree