LeetCode #100 Same Tree 相同的二元樹

Klook.com
文章觀看次數: 252

LeetCode題目翻譯

英文原文如下

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.

中文翻譯

給予兩個二元樹的根結點  p 跟 q ，寫一個函式來確認它們相同與否。

要是兩個二元樹結構上及每個節點的值都相同，則它們被視為相同的。

範例及題目限制

這一題的範例應該不用特別解釋吧，圖示上看起來就不一樣了 d(`･∀･)b

解題思路

這一題的解決方法也不難，要寫一個 Recursion (遞迴) 的程式去遍歷整顆樹

在每一次的遞迴中，要是

  • p 跟 q 節點都是null 回傳 true
  • p 跟 q 節點只有一個是null 回傳 false
  • p 跟 q 節點值不相同的話回傳 false

為什麼 p跟q節點值相同的話沒有回傳true呢?

那是因為要是值相同，代表兩個節點都不為null，意思就是可能會有底下的左或右節點

所以要繼續往下遞迴確認，直到該分支到底為止

C# 解決方案 

public class Solution {
    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;
        }

        return IsSameTree(p.left, q.left) && IsSameTree(p.right, q.right);
    }
}

Java 解決方案 

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);
    }
}

Python3 解決方案 

class Solution:
    def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
        if(p==None and q==None):
            return True
        
        if(p==None or q==None):
            return False
        
        if(p.val != q.val):
            return False
        
        return self.isSameTree(p.left, q.left) and  self.isSameTree(p.right, q.right)

JavaScript 解決方案 

var isSameTree = function(p, q) {
    if(!p && !q)
    {
        return true;
    }

    if(!p || !q)
    {
        return false;
    }

    if(p.val != q.val)
    {
        return false;
    }

    return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
};

結論

二元樹的概念總是有點麻煩的，每次看到都頭痛一次…

🧡如果這篇文章有幫上你的一點點忙，那是我的榮幸

🧡幫我分享或是收藏，我都會很感激的

✅如有任何疑問，歡迎透過留言或messenger讓我知道 !

題目連結 : Same Tree – LeetCode

相關文章

隨機文章

相關文章

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。 必填欄位標示為 *