樹的子結構
前言
給定兩顆二叉樹A和B,如何判斷B是不是A的子結構,本文將分享一個方案用來解決此問題,歡迎各位感興趣的開發者閱讀本文。
思路分析
在我的資料結構與演算法實現系列文章——實現二叉搜尋樹中,我們知道了二叉樹最多隻能有兩個子節點:左子節點、右子節點。那麼,在本題中要判斷是否包含,可以分為兩步來實現:
- 在樹A中找到和樹B的根節點的值一樣的節點R
- 如果樹A的節點與樹B的根結點相同,則執行進一步的判斷(比對兩棵樹的子結構)得出比對結果
-
如果得出的結果為false,分別遞迴樹A的左子節點與右子節點跟樹B進行比對,直至任意一棵樹的葉子節點
-
判斷樹A中以R為根節點的子樹是否包含和樹B一樣的結構
- 如果樹B為null則代表樹A中包含樹B,返回true
- 如果樹A為null則代表樹A中不包含樹B,返回false
- 如果比對的兩個節點不等,則代表當前A的子樹中不包含樹B結構,返回false
- 否則,繼續執行遞迴,直至任意一棵樹的葉子節點
實現程式碼
通過上個章節的分析,我們已經得出了具體的思路,接下來,我們就將思路轉換為程式碼,如下所示:
- 實現主函式,判斷B是否為A的子結構:
- 遞迴樹A將其與樹B的節點進行比對,找到相同的節點再做進一步的比對
```typescript export function TreeSubstructure( treeA: BinaryTreeNode | null | undefined, treeB: BinaryTreeNode | null | undefined ): boolean { let result = false; if (treeA != null && treeB != null) { // 兩個節點相同 if (treeA.key === treeB.key) { // 判斷樹A中是否包含樹B result = treeAHaveTreeB(treeA, treeB); }
// 繼續尋找左子樹與右子樹
if (!result) {
result = TreeSubstructure(treeA?.left, treeB);
}
if (!result) {
result = TreeSubstructure(treeA?.right, treeB);
}
} return result; } ```
- 實現進一步的比對函式,判斷樹A的子節點中是否包含跟樹B一樣的結構
```typescript function treeAHaveTreeB( treeA: BinaryTreeNode | null | undefined, treeB: BinaryTreeNode | null | undefined ): boolean { // 遞迴到了樹B的葉節點,代表該節點存在於樹A中 if (treeB == null) { return true; } // 遞迴到樹A的葉節點,代表該節點不存在於樹A中 if (treeA == null) { return false; } if (treeA.key !== treeB.key) { return false; } // 左子樹與右子樹都相同 return ( treeAHaveTreeB(treeA?.left, treeB?.left) && treeAHaveTreeB(treeA?.right, treeB?.right) ); }
```
注意:上述程式碼中用到了遞迴,如果你對其不瞭解,可以移步我的另一篇文章:遞迴的理解與實現
程式碼中還用到了一個自定義型別BinaryTreeNode,具體的型別定義請移步示例程式碼章節。
測試用例
接下來,我們用思路分析章節中所舉的例子來測試下上述函式能否正確執行。
```typescript const treeA: BinaryTreeNode = { key: 8, left: { key: 8, left: { key: 9 }, right: { key: 2, left: { key: 4 }, right: { key: 7 } } }, right: { key: 7 } };
const treeB: BinaryTreeNode = { key: 8, left: { key: 9 }, right: { key: 2 } };
const result = TreeSubstructure(treeA, treeB); console.log("treeA中包含treeB", result);
```
示例程式碼
本文所用程式碼完整版請移步👇:
寫在最後
至此,文章就分享完畢了。
我是神奇的程式設計師,一位前端開發工程師。
如果你對我感興趣,請移步我的個人網站,進一步瞭解。
- 文中如有錯誤,歡迎在評論區指正,如果這篇文章幫到了你,歡迎點贊和關注😊
- 本文首發於神奇的程式設計師公眾號,未經許可禁止轉載💌
- Web端高分屏圖片載入方案
- 樹的子結構
- 合併兩個排序的連結串列
- 實現連結串列反轉
- 獲取連結串列中倒數第K個節點
- 動態轉換圖片格式為webp
- 調整陣列元素順序演算法
- 實現TypeScript中的互斥型別
- 實現TypeScript中的互斥型別
- 實現數值校驗演算法
- 我離職了
- 實現正則表示式匹配演算法
- Go defer的一些神奇規則,你瞭解嗎?
- 實現nest的自定義註解
- 數值的整數次方
- 二進位制中1的個數
- 為程式設計師添上“翅膀”的機器學習軟體 Codex 有多神奇
- 很久很久以前,有一臺神奇的機器···
- 移動開發必知:Kotlin裡面一個神奇的BUG(勸官方早點修復)
- 使用Vue3的CompositionAPI來優化程式碼量