JS刷演算法題：二叉樹
- 2020 年 2 月 18 日
- 筆記
Q1.翻轉二叉樹（easy）
如題所示
示例： 輸入： 4 / 2 7 / / 1 3 6 9 輸出： 4 / 7 2 / / 9 6 3 1 來源：力扣（LeetCode） 鏈接：https://leetcode-cn.com/problems/invert-binary-tree
這道題目起源於一個非常搞笑的事件：據說大名鼎鼎的Mac軟體包管理工具Homebrew的作者，因為做不出這道在leetcode上難度為easy的題，被Google公司拒了。。。
Google：我們90％的工程師使用您編寫的軟體(Homebrew)，但是您卻無法在面試時在白板上寫出翻轉二叉樹這道題，這太糟糕了。
如何看待 Max Howell 被 Google 拒絕？www.zhihu.com
格式要求
/** * Definition for a binary tree node. * function TreeNode(val) { * this.val = val; * this.left = this.right = null; * } */ /** * @param {TreeNode} root * @return {TreeNode} */ var invertTree = function(root) { // 編碼 };
分析：二叉樹遍歷
思路就是遍歷二叉樹的每一個節點，然後把左右鏈接替換一下就可以了。前序/中序/後序 都可以。如下所示
具體程式碼
var invertTree = function(root) { traveral(root); return root; }; function traveral(node) { if (node === null) return; traveral(node.left); traveral(node.right); const temp = node.right; node.right = node.left; node.left = temp; }
Q2.二叉樹的右視圖(middle)
給定一棵二叉樹，想像自己站在它的右側，按照從頂部到底部的順序，返回從右側所能看到的節點值。
輸入: [1,2,3,null,5,null,4] 輸出: [1, 3, 4] 解釋: 1 <--- / 2 3 <--- 5 4 <--- 輸入: [1,2,3,null,5,null,null] 輸出: [1, 3, 5] 解釋: 1 <--- / 2 3 <--- 5 <--- 來源：LeetCode 鏈接：https://leetcode-cn.com/problems/binary-tree-right-side-view
格式要求
/** * Definition for a binary tree node. * function TreeNode(val) { * this.val = val; * this.left = this.right = null; * } */ /** * @param {TreeNode} root * @return {number[]} */ var rightSideView = function(root) { // 編碼 }
分析：層序遍歷
題目的思路很明顯，對二叉樹進行層序遍歷，然後取得每一層的最後一個節點。放到一個數組裡最後返回。
1.我們可以設置一個隊列存放依次遍歷的節點對象。
2.使用兩層循環
- 內層循環通過不斷出隊列的方式遍歷當前層的節點，同時通過左右鏈接收集下一層節點
- 外層循環判斷隊列長度>0時就繼續運行，從而實現逐層迭代
3.在每次內層循環中獲取最右端的非空節點
具體程式碼
var rightSideView = function(root) { if (!root) return []; const queue = []; const arrRS = []; // 先保存根結點，也就是第一層二叉樹 queue.push(root); while (queue.length > 0) { // 將隊列長度先保存到一個變數裡面 // 表示的是上一層的節點的數量 let length = queue.length; let temp = null; // 遍歷上一層節點，將它們的子節點加入隊列中，收集得到二叉樹的下一層 for (let i = 0; i < length; i++) { // 出隊列，並獲得返回的父節點 const node = queue.shift(); // 每次都用當前節點的val覆蓋temp // temp最後會等於當前層最右的一個非空節點的val值 if (node.val) temp = node.val; // 收集當前節點的左節點和右節點，從而得到下一層 if (node.left) queue.push(node.left); if (node.right) queue.push(node.right); } // 收集每一層的最右節點 arrRS.push(temp); } return arrRS; };
Q3.二叉樹中的最大路徑和(difficult)
給定一個非空二叉樹，返回其最大路徑和。
本題中，路徑被定義為一條從樹中任意節點出發，達到任意節點的序列。該路徑至少包含一個節點，且不一定經過根節點。
示例1: 輸入: [1,2,3] 1 / 2 3 輸出: 6 示例2: 輸入: [-10,9,20,null,null,15,7] -10 / 9 20 / 15 7 輸出: 42 來源：LeetCode 鏈接：https://leetcode-cn.com/problems/binary-tree-maximum-path-sum/
格式要求
/** * Definition for a binary tree node. * function TreeNode(val) { * this.val = val; * this.left = this.right = null; * } */ /** * @param {TreeNode} root * @return {number} */ var maxPathSum = function(root) { // 編碼 };
思路分析
1.整體思路：通過後序遍歷，自底向上計算。
因為後序遍歷的計算過程是：左節點-右節點-根結點。 所以通過這種遍歷方式，我們可以在計算兩個子節點的基礎上，推斷當這兩個節點到父節點的最大路徑和。然後不斷向上累加，去計算最大值。
同時在每個節點都通過Math.max更新當前的最大值，直到回歸到根結點的時候，也就能比較出最大值來了。
2.路徑的單一性： 當一個節點是只是作為一個中間節點，而不是一個根節點的時候：左節點和右節點只能選擇一個作為經過的路徑。 因為路徑是「單一」的而不是「分叉」的
例如下面的圖示中， 當我們通過比較選擇9-7-10這條的時候，節點8就不在路徑內了
3.根節點的連接性：當一個節點作為根節點的時候，它可以將兩個子樹的路徑連接起來
4. 對於兩個子節點的累加值A，B，分3種情況討論
- A>0,B>0: 選擇Math.max(A,B)作為經過路徑
- A>0,B<0: 選擇A作為經過路徑
- A<0,B>0: 選擇B作為經過路徑
- A<0,B<0: A,B都不選
綜上所述
我們的思路是：
- 後序遍歷，自底向上計算
- 對於每個節點，假設它是根結點，計算它聯合兩個子樹路徑後的最大值
- 對於每個節點，假設它是中間節點，選擇兩條中較大的一條子樹作為路徑
- 對於2，3分上面的四種情況進行分別處理
具體程式碼
// 1.考慮全為負數的情況 // 2.考慮當前節點為負的情況 let max = Number.MIN_VALUE; var maxPathSum = function(root) { max = root.val; traveral(root); return max; }; function traveral(node) { if (node === null) return 0; const a = traveral(node.left); const b = traveral(node.right); let v = node.val; if (a >= 0 && b >= 0) { max = Math.max(max, v + a + b); v += Math.max(a, b); } else if (a >= 0) { max = Math.max(max, v + a); v += a; } else if (b >= 0) { max = Math.max(max, v + b); v += b; } return v; } function TreeNode(val) { this.val = val; this.left = this.right = null; }
本文完
