劍指Offer——樹的子結構（JS實作）

題目描述

解題思路

• 本題采用兩個遞歸互相調用的方式進行求解
• 一個樹是否是另一個樹的子結構，有3種情況
• 情況一：子樹和目前節點完全一緻
• 情況二：子樹在左子樹中
• 情況三：子樹在右子樹中
• 第一個遞歸用于控制發生的是哪一種情況
• 第二個遞歸則用于進行周遊，如果A樹為空，說明A數周遊完了都沒有比對到，說明B樹不是子樹，如果B樹為空，說明B樹周遊完了，說明B樹是子樹，如果A和B的值不相同，則傳回false,此時也許會有疑問，那萬一子結構在樹的深部豈不是直接傳回false了？這是第一個遞歸就開始發揮作用了。
• 本題的難點在于：如果隻有一個遞歸，當A和B的值不同時，若直接傳回false，顯然不合理，但是如果不傳回false，後續很難進行

解題代碼

var isSubStructure = function(A, B) {
    // 判斷是否是樹的子結構有兩種情況
    // 情況1：目前節點是子結構
    // 情況2：目前節點的左右子樹是子結構
    // 如果A節點為空，或者B節點為空，都說明不是子樹
    if (!A || !B) {
        return false;
    }
    return (dfs(A,B) || isSubStructure(A.left,B) || isSubStructure(A.right,B));

    function dfs(A,B) {
        // 如果B的節點為空，說明B已經周遊完了，說明此時B是A的子結構
        if (!B) {
            return true;
        }
        // 如果A都周遊完了，說明B不是子結構
        if (!A) {
            return false;
        }
        // 如果目前節點不同，則傳回false
        if (A.val !== B.val) {
            return false;
        }
        // 目前節點相同，還要判斷目前節點的左右子樹是否都相同
        return (dfs(A.left,B.left) && dfs(A.right,B.right));
        
    }
};
      

總結（本題給我們的啟示思路）

• 啟示一：學會使用兩個遞歸進行互補計算
• 啟示二：多考慮邊界條件