【小Y學演算法】??每日LeetCode打卡??——26.相同的樹

📢前言

• 🌲 每天打卡一道演算法題，既是一個學習程序，又是一個分享的程序😜
• 🌲 提示：本專欄解題 編程語言一律使用 C# 和 Java 兩種進行解題
• 🌲 要保持一個每天都在學習的狀態，讓我們一起努力成為演算法大神吧🧐！
• 🌲 今天是力扣演算法題持續打卡第26天🎈！

🌲原題樣例

給你兩棵二叉樹的根節點 p 和 q ，撰寫一個函式來檢驗這兩棵樹是否相同，

如果兩個樹在結構上相同，并且節點具有相同的值，則認為它們是相同的，

示例 1:

輸入：p = [1,2,3], q = [1,2,3]
輸出：true

示例 2:

輸入：p = [1,2], q = [1,null,2]
輸出：false

示例 3：

輸入：p = [1,2,1], q = [1,1,2]
輸出：false

提示：

• 兩棵樹上的節點數目都在范圍 [0, 100] 內
• -104 <= Node.val <= 104

🌻C#方法：遞回

思路決議

根據題意我們知道，最終目的就是 判斷是不是相同的樹

遞回，前序遍歷對比是否為相同的樹

代碼：

public class Solution {
public bool IsSameTree(TreeNode p, TreeNode q)
        {
            //遞回終止情況1：p, q都是null
            if (p == null && q == null)
            {
                return true;
            }
            //遞回終止情況2：p, q中有一個為空，或者是p, q的節點值不等
            else if (p == null || q == null || p.val != q.val)
            {
                return false;
            }
            else
            {
                //遞回看左子樹是否相同
                bool isLeftSameTree = IsSameTree(p.left, q.left);
                //遞回看右子樹是否相同
                bool isRightSameTree = IsSameTree(p.right, q.right);
                return isLeftSameTree && isRightSameTree;
            }
        }
}

執行結果

通過
執行用時：92 ms，在所有 C# 提交中擊敗了49.73%的用戶
記憶體消耗：24.4 MB，在所有 C# 提交中擊敗了38.50%的用戶

復雜度分析

時間復雜度：O(min(m+n))
空間復雜度：O(min(m+n))

🌻Java 方法一：深度優先搜索

思路決議
如果兩個二叉樹都為空，則兩個二叉樹相同，如果兩個二叉樹中有且只有一個為空，則兩個二叉樹一定不相同，

如果兩個二叉樹都不為空，那么首先判斷它們的根節點的值是否相同，若不相同則兩個二叉樹一定不同，若相同，再分別判斷兩個二叉樹的左子樹是否相同以及右子樹是否相同，

這是一個遞回的程序，因此可以使用深度優先搜索，遞回地判斷兩個二叉樹是否相同，

代碼：

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        for (int i = 0; i != n; ++i) {
            nums1[m + i] = nums2[i];
        }
        Arrays.sort(nums1);
    }
}

執行結果

通過
執行用時：0 ms，在所有 Java  提交中擊敗了100.00%的用戶
記憶體消耗：35.8 MB，在所有 Java 提交中擊敗了53.34%的用戶

復雜度分析

時間復雜度：O(min(m+n))其中 mm 和 nn 分別是兩個二叉樹的節點數，對兩個二叉樹同時進行深度優先搜索，只有當兩個二叉樹中的對應節點都不為空時才會訪問到該節點，因此被訪問到的節點數不會超過較小的二叉樹的節點數，

空間復雜度：O(min(m+n))其中 mm 和 nn 分別是兩個二叉樹的節點數，空間復雜度取決于遞回呼叫的層數，遞回呼叫的層數不會超過較小的二叉樹的最大高度，最壞情況下，二叉樹的高度等于節點數，

🌻Java 方法二：廣度優先搜索

思路決議

也可以通過廣度優先搜索判斷兩個二叉樹是否相同，同樣首先判斷兩個二叉樹是否為空，如果兩個二叉樹都不為空，則從兩個二叉樹的根節點開始廣度優先搜索，

使用兩個佇列分別存盤兩個二叉樹的節點，初始時將兩個二叉樹的根節點分別加入兩個佇列，每次從兩個佇列各取出一個節點，進行如下比較操作，

1. 比較兩個節點的值，如果兩個節點的值不相同則兩個二叉樹一定不同；
2. 如果兩個節點的值相同，則判斷兩個節點的子節點是否為空，如果只有一個節點的左子節點為空，或者只有一個節點的右子節點為空，則兩個二叉樹的結構不同，因此兩個二叉樹一定不同；
3. 如果兩個節點的子節點的結構相同，則將兩個節點的非空子節點分別加入兩個佇列，子節點加入佇列時需要注意順序，如果左右子節點都不為空，則先加入左子節點，后加入右子節點，

如果搜索結束時兩個佇列同時為空，則兩個二叉樹相同，如果只有一個佇列為空，則兩個二叉樹的結構不同，因此兩個二叉樹不同，

代碼：

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int p1 = 0, p2 = 0;
        int[] sorted = new int[m + n];
        int cur;
        while (p1 < m || p2 < n) {
            if (p1 == m) {
                cur = nums2[p2++];
            } else if (p2 == n) {
                cur = nums1[p1++];
            } else if (nums1[p1] < nums2[p2]) {
                cur = nums1[p1++];
            } else {
                cur = nums2[p2++];
            }
            sorted[p1 + p2 - 1] = cur;
        }
        for (int i = 0; i != m + n; ++i) {
            nums1[i] = sorted[i];
        }
    }
}

執行結果

通過
執行用時：0 ms，在所有 Java  提交中擊敗了100%的用戶
記憶體消耗：35.7 MB，在所有 Java 提交中擊敗了72.26%的用戶

復雜度分析

時間復雜度：O(min(m+n))
空間復雜度：O(min(m+n))

💬總結

• 今天是力扣演算法題打卡的第二十六天！
• 文章采用 C#和 Java 兩種編程語言進行解題
• 一些方法也是參考力扣大神寫的，也是邊學習邊分享，再次感謝演算法大佬們
• 那今天的演算法題分享到此結束啦，明天再見！
  

🚀往期優質文章分享

• ??Unity零基礎到入門 | 游戲引擎 Unity 從0到1的 系統學習 路線【全面總結-建議收藏】！
• 🧡花一天時間做一個高質量飛機大戰游戲，過萬字Unity完整教程！漂亮學妹看了直呼666！
• 💛回憶童年和小伙伴一起玩過的經典游戲【炸彈人小游戲】制作程序+決議
• 💚通宵一晚做出來的一款類似CS的第一人稱射擊游戲Demo！原來做游戲也不是很難
• 🤍爆肝整整一個周末寫一款類似 皇室戰爭 的 即時戰斗類 游戲Demo！兩萬多字游戲制作程序+決議！
• 💙一款類似“恐龍快打”的 橫版街機格斗游戲 該如何制作？| 一起來學習 順便送原始碼【碼文不易，建議收藏學習】
• 💜【超實用技巧】| 提高寫文的質量 和 速率必學技能： Typora 圖床配置 詳細說明