TypeScript判斷對稱的二叉樹方案詳解
前言
如果一顆二叉樹和它的鏡像一樣，那么它就是對稱的。實現(xiàn)一個函數(shù)用于判斷一顆二叉樹是否對稱，你會怎么做？
本文將分享一種解決方案，歡迎各位感興趣的開發(fā)者閱讀本文。
實現(xiàn)思路
在上一篇文章二叉樹的鏡像中我們知道了此問題的解決方案是前序遍歷，那么我們可以修改下前序遍歷算法，父節(jié)點遍歷后，先遍歷它的右子節(jié)點，再遍歷它的左子節(jié)點，我們把這種算法稱為：對稱前序遍歷
如下圖所示的兩棵樹，我們分別列舉下兩種遍歷的結(jié)果：
- 樹A：
- 前序遍歷：8, 6, 5, 7, 6, 7, 5
- 對稱前序遍歷：8, 6, 5, 7, 6, 7, 5
- 樹B：
- 前序遍歷：8, 6, 5, 7, 9, 7, 5
- 對稱前序遍歷：8, 9, 5, 7, 6, 7, 5
經(jīng)過對比后，我們發(fā)現(xiàn)樹A的兩種遍歷方法得到的結(jié)果是一樣的，那么它就是對稱的；樹B的結(jié)果不同，它就不是對稱的。
如果有一顆不完全二叉樹，它的所有節(jié)點都相同，他是對稱的嗎？
針對于這種情況，我們就需要將它缺省的null節(jié)點進行補齊了，補齊后的兩種遍歷結(jié)果為：
- 前序遍歷：7, 7, 7, null, null, 7, null, null, 7, 7, null, null, null
- 對稱前序遍歷：7, 7, null, 7, null, null, 7, 7, null, null, 7, null, null
對比兩個結(jié)果后，我們發(fā)現(xiàn)并不一樣，那么它就不是對稱的。
實現(xiàn)代碼
有了思路后，接下來我們看下代碼實現(xiàn)，如下所示：
- 從樹的根節(jié)點出發(fā)，遞歸比對它的左子節(jié)點和右子節(jié)點
- 比對過程中：
- 二者都到達葉子結(jié)點，代表這棵樹是對稱的
- 任意一方到達葉子結(jié)點，代表這棵樹不對稱
- 節(jié)點值不同，這棵樹不對稱
export function SymmetricBinaryTree(node: BinaryTreeNode | null): boolean {
return isSymmetrical(node, node);
}
function isSymmetrical(
node: BinaryTreeNode | null | undefined,
cloneNode: BinaryTreeNode | null | undefined
): boolean {
// 到達葉子節(jié)點，兩者都為nul代表節(jié)點相同
if (node == null && cloneNode == null) {
return true;
}
// 任意一方到達葉子節(jié)點，代表節(jié)點不同
if (node == null || cloneNode == null) {
return false;
}
// 節(jié)點值不同
if (node.key != cloneNode.key) {
return false;
}
// 分別比對樹的左子節(jié)點和右子節(jié)點
return (
isSymmetrical(node.left, cloneNode.right) &&
isSymmetrical(node.right, cloneNode.left)
);
}
接下來，我們以上個章節(jié)列舉的例子為例，將其帶入上述代碼，驗證下能否正確判斷，如下所示：
const tree: BinaryTreeNode = {
key: 8,
left: {
key: 6,
left: { key: 5 },
right: { key: 7 }
},
right: { key: 6, left: { key: 7 }, right: { key: 5 } }
};
const isSymmetric = SymmetricBinaryTree(tree);
console.log(tree, "是否為對稱二叉樹: ", isSymmetric);
示例代碼
本文所用代碼完整版請移步??：
以上就是TypeScript實現(xiàn)對稱的二叉樹詳解的詳細內(nèi)容，更多關于TypeScript 對稱二叉樹的資料請關注腳本之家其它相關文章！
相關文章
詳解什么是TypeScript里的Constructor?signature
這篇文章主要介紹了什么是TypeScript里的Constructor?signature詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪2023-07-07
TypeScript的基礎語法,包括變量聲明、復合類型（數(shù)組和對象）、條件控制（if-else和switch）、循環(huán)（for和while）、函數(shù)（基礎和箭頭函數(shù),以及可選參數(shù)）、面向?qū)ο筇匦裕杜e、接口、繼承）以及模塊開發(fā)中的導出和導入2024-07-07
這篇文章主要為大家介紹了基于DS-SDK封裝ThreeJS的三維場景核心庫Viewer封裝示例詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪2022-10-10
這篇文章主要為大家介紹了type-challenge刷題(easy部分)示例詳解,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進步,早日升職加薪2023-08-08
Typescript編碼規(guī)范ESLint和Prettier使用示例詳解
這篇文章主要介紹了Typescript編碼規(guī)范ESLint和Prettier使用示例詳解,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進步,早日升職加薪2023-09-09
這篇文章主要為大家介紹了TypeScript之Generics泛型類型學習，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪2023-07-07
這篇文章主要為大家介紹了Nest框架中集成使用Swagger的示例說明，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪2022-08-08
這篇文章主要為大家介紹了Rollup 簡易入門示例教程，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪2023-02-02
postman數(shù)據(jù)加解密實現(xiàn)APP登入接口模擬請求
對于Postman的使用，一般情況下只要發(fā)發(fā)確定的請求與參數(shù)就可以的了,然而，在使用的時候，尤其是接口測試時，請求接口的設計里面都有數(shù)據(jù)加密，參數(shù)驗簽，返回數(shù)據(jù)也有進行加密的，這個時候就需要使用一些腳本做處理，模擬app登入請求的操作2021-08-08
TypeScript實現(xiàn)類型安全的EventEmitter
這篇文章主要為大家介紹了TypeScript實現(xiàn)類型安全的EventEmitter示例詳解有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪2023-03-03