資訊專欄INFORMATION COLUMN
摘要：參考自對稱的二叉樹公眾號秘密花園對稱二叉樹非對稱二叉樹實現思路判斷根節點相同左子樹的右節點和右子樹的左節點相同右子樹的左節點和左子樹的右節點相同步驟模擬一個對稱二叉樹和非對稱二叉樹對稱二叉樹非對稱二叉樹步驟利用遞歸實現對稱二叉樹判斷判斷兩個
參考自ConardLi： 《對稱的二叉樹》 公眾號： code秘密花園
對稱二叉樹:
8
/
6 6
/ /
5 7 7 5
非對稱二叉樹:
8
/
6 5
/ /
5 7 7 5
實現思路:
判斷根節點相同
左子樹的右節點和右子樹的左節點相同
右子樹的左節點和左子樹的右節點相同
步驟1: 模擬一個對稱二叉樹和非對稱二叉樹
//對稱二叉樹
const symmetricalTree = {
val: 8,
left: {
val: 6,
left: { val: 5, left: null, right: null },
right: { val: 7, left: null, right: null }
},
right: {
val: 6,
left: { val: 7, left: null, right: null },
right: { val: 5, left: null, right: null }
}
}
//非對稱二叉樹
const binaryTree = {
val: 8,
left: {
val: 6,
left: { val: 5, left: null, right: null },
right: { val: 7, left: null, right: null }
},
right: {
val: 9,
left: { val: 7, left: null, right: null },
right: { val: 5, left: null, right: null }
}
}
步驟2: 利用遞歸實現對稱二叉樹判斷
function isSymmetrical(pRoot) {
return isSymmetricalTree(pRoot, pRoot);
}
function isSymmetricalTree(node1, node2) {
//判斷兩個節點都是否為空
if (!node1 && !node2) {
return true;
}
//判斷兩個節點是否存在一個為空
if (!node1 || !node2) {
return false;
}
//判斷兩個節點是否相同
if (node1.val != node2.val) {
return false;
}
return isSymmetricalTree(node1.left, node2.right) && isSymmetricalTree(node1.right, node2.left);
}
輸出:
console.log(isSymmetrical(symmetricalTree)); console.log(isSymmetrical(binaryTree));
結果如下:
true false
參考自ConardLi： 《對稱的二叉樹》 公眾號： code秘密花園
文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。
轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/104980.html
摘要：另外，由于篇幅有限，本篇的重點在于二叉樹的常見算法以及實現。常見的二叉樹實現代碼之前寫過相關的文章，是關于如何創建及遍歷二叉樹的，這里不再贅述。同時我們注意到，在二叉樹深度比較大的時候，我們光是比較左右是不夠的。 本篇為復習過程中遇到過的總結，同時也給準備面試的同學一份參考。另外，由于篇幅有限，本篇的重點在于二叉樹的常見算法以及實現。 常見的二叉樹實現代碼 之前寫過相關的文章，是關于如...
摘要：題目描述請實現一個函數，用來判斷一顆二叉樹是不是對稱的。注意，如果一個二叉樹同此二叉樹的鏡像是同樣的，定義其為對稱的。分析一般關于二叉樹的題目，第一直覺是往遞歸上面靠，當然了，本題適不適合還暫時不知道。 題目描述 請實現一個函數，用來判斷一顆二叉樹是不是對稱的。注意，如果一個二叉樹同此二叉樹的鏡像是同樣的，定義其為對稱的。 分析 一般關于二叉樹的題目，第一直覺是往遞歸上面靠，當然了，本...
閱讀 1697·2021-10-09 09:44
閱讀 3263·2021-09-27 13:36
閱讀 1520·2021-09-22 15:33
閱讀 1274·2021-09-22 15:23
閱讀 1159·2021-09-06 15:02
閱讀 1695·2019-08-29 16:14
閱讀 2901·2019-08-29 15:26
閱讀 2408·2019-08-28 18:08
