[TOC] # 1.重建二叉樹 [牛客網鏈接](https://www.nowcoder.com/practice/8a19cbe657394eeaac2f6ea9b0f6fcf6?tpId=13&tqId=11157&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking) 題目描述：輸入某二叉樹的前序遍歷和中序遍歷的結果，請重建出該二叉樹。假設輸入的前序遍歷和中序遍歷的結果中都不含重復的數字。例如輸入前序遍歷序列 {1,2,4,7,3,5,6,8} 和中序遍歷序列 {4,7,2,1,5,3,8,6}，則重建二叉樹并返回。 解題思路： 前序序列第一個數將中序序列劃分為根和左右子樹，遞歸地利用這個規律來構建二叉樹 ``` function TreeNode(x) { this.val = x; this.left = null; this.right = null; } function reConstructBinaryTree(pre, vin) { // write code here if (pre.length === 0 || vin.length === 0) return null // slice劃分時越界會返回[] let root = new TreeNode(pre[0]) let index = vin.indexOf(pre[0]) root.left = reConstructBinaryTree(pre.slice(1, index+1), vin.slice(0, index)) root.right = reConstructBinaryTree(pre.slice(index + 1), vin.slice(index+1)) return root } ``` # 2.樹的子結構 [牛客網鏈接](https://www.nowcoder.com/practice/6e196c44c7004d15b1610b9afca8bd88?tpId=13&tqId=11170&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking) 題目描述：輸入兩棵二叉樹 A，B，判斷 B 是不是 A 的子結構。（ps：我們約定空樹不是任意一個樹的子結構） 解題思路：遞歸：首先判斷根結點的值是否相等，如果相等則進一步判斷左右結點是否相等，否則判斷 A 的左子樹是否包含B（true 的話則會返回，false 則會繼續判斷右邊），A 的右子樹是否包含 B，另外注意 null 是非 null 樹的子結構 ``` function isSubTree(pA, pB) { if (pB === null) return true // 空的話肯定是A的子樹，注意優先判斷pB if (pA === null) return false // 判斷B是否為A的子樹，A為空的話肯定不是了 if (pA.val === pB.val) { return isSubTree(pA.left, pB.left) && isSubTree(pA.right, pB.right) // 短路特性,同時為true才為true } else { return false } } function HasSubtree(pRoot1, pRoot2) { // write code here if (pRoot1 === null || pRoot2 === null) return false return isSubTree(pRoot1, pRoot2) || HasSubtree(pRoot1.left, pRoot2) || HasSubtree(pRoot1.right, pRoot2) } ``` # 3.二叉樹的鏡像 [牛客網鏈接](https://www.nowcoder.com/practice/564f4c26aa584921bc75623e48ca3011?tpId=13&tqId=11171&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking) 題目描述：操作給定的二叉樹，將其變換為源二叉樹的鏡像。  解題思路：遞歸：先交換最下層的結點的左右子樹，再交換上層的左右子樹 ``` function Mirror(root) { // write code here if (root === null) return null if (root.left !== null) { Mirror(root.left) } if (root.right !== null) { Mirror(root.right) } if (root.left === null && root.right === null) return let tmp = root.left root.left = root.right root.right = tmp return root } ``` # 4.從上往下打印二叉樹 [牛客網鏈接](https://www.nowcoder.com/practice/7fe2212963db4790b57431d9ed259701?tpId=13&tqId=11175&tPage=2&rp=2&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking) 題目描述：從上往下打印出二叉樹的每個節點，同層節點從左至右打印。 解題思路：使用隊列，先放入根結點，再放入左右子結點，廣搜 ``` function PrintFromTopToBottom(root) { // write code here let queue = [] const res = [] if (root === null) return res queue.push(root) // 隊列->層次遍歷 while(queue.length !== 0) { let top = queue.shift() res.push(top.val) if (top.left !== null) { queue.push(top.left) } if (top.right !== null) { queue.push(top.right) } } return res } ``` # 5.二叉搜索樹（BST）的后序遍歷序列 [牛客網鏈接](https://www.nowcoder.com/practice/a861533d45854474ac791d90e447bafd?tpId=13&tqId=11176&tPage=2&rp=2&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking) 題目描述：輸入一個整數數組，判斷該數組是不是某二叉搜索樹的后序遍歷的結果。如果是則輸出Yes,否則輸出No。假設輸入的數組的任意兩個數字都互不相同。 ``` function VerifySquenceOfBST(sequence) { // write code here // BST特性：左子結點比根結點小，右子結點大于根結點 let size = sequence.length if (size === 0) return false let i = 0 while (--size) { // "根"總為數組最后一個元素 while (sequence[i++] < sequence[size]); // 左子樹都應該小于根元素 while (sequence[i++] > sequence[size]); // 右子樹都應該大于根元素 if (i < size) return false // 理論上上面兩個循環都應該到達最后一個元素 i = 0 } return true } ``` 解題思路：非遞歸方法 -> 看注釋 # 6.二叉樹中和為某一個值的路徑 [牛客網鏈接](https://www.nowcoder.com/practice/b736e784e3e34731af99065031301bca?tpId=13&tqId=11177&tPage=2&rp=2&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking) 題目描述：輸入一顆二叉樹的跟節點和一個整數，打印出二叉樹中結點值的和為輸入整數的所有路徑。路徑定義為從樹的根結點開始往下一直到葉結點所經過的結點形成一條路徑。(注意: 在返回值的list中，數組長度大的數組靠前) 解題思路：dfs的思想，關鍵是路徑的保存；注意題目中“路徑”指的是到達葉結點的，中間結點不用判斷，整體思路：如果為葉結點則判斷累計的和是否與指定的數相等，如果相等，則添加當前路徑；dfs的時候注意返回的時候路徑彈出當前結點。 ``` var path; var stack; function FindPath(root, expectNumber) { // write code here if(root == null){ return []; } path= []; stack = []; cal(root,expectNumber); return path; } function cal(root,expectNumber){ stack.push(root.val); if(root.val == expectNumber && root.left==null && root.right==null){ path.push(stack.slice()); } else{ if(root.left!=null){ cal(root.left,expectNumber-root.val); } if(root.right!=null){ cal(root.right,expectNumber-root.val); } } stack.pop(); } ``` # 7.二叉樹的深度 題目描述：輸入一棵二叉樹，求該樹的深度。從根結點到葉結點依次經過的結點（含根、葉結點）形成樹的一條路徑，最長路徑的長度為樹的深度。 ```js var maxDepth = function (root) { if (root === undefined || root === null) { return 0 } return Math.max(maxDepth(root.left),maxDepth(root.right)) + 1 } ``` # 8.平衡二叉樹 [牛客網鏈接](https://www.nowcoder.com/practice/8b3b95850edb4115918ecebdf1b4d222?tpId=13&tqId=11192&tPage=2&rp=2&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking) 題目描述：輸入一棵二叉樹，判斷該二叉樹是否是平衡二叉樹。 平衡二叉搜索樹（Self-balancing binary search tree）又被稱為AVL樹（有別于AVL算法），且具有以下性質：它是一 棵空樹或它的左右兩個子樹的高度差的絕對值不超過1，并且左右兩個子樹都是一棵平衡二叉樹。平衡二叉樹的常用實現方法有紅黑樹、AVL、替罪羊樹、Treap、伸展樹等。 最小二叉平衡樹的節點總數的公式如下 F(n)=F(n-1)+F(n-2)+1 這個類似于一個遞歸的數列，可以參考Fibonacci(斐波那契)數列，1是根節點，F(n-1)是左子樹的節點數量，F(n-2)是右子樹的節點數量。 ``` // 平衡二叉樹：左右子樹高度差不超過1，且左右子樹也是平衡二叉樹 function IsBalanced_Solution(pRoot) { // write code here if (pRoot === null) return true let leftTreeDeep = getDeep(pRoot.left) let rightTreeDeep = getDeep(pRoot.right) if (Math.abs(leftTreeDeep - rightTreeDeep) > 1) { return false } return IsBalanced_Solution(pRoot.left) && IsBalanced_Solution(pRoot.right) } // 獲取樹的高度 function getDeep(root) { if (root === null) return 0 let left = getDeep(root.left) let right = getDeep(root.right) return left > right ? left + 1 : right + 1 } ``` # 9.對稱的二叉樹 [牛客網鏈接](https://www.nowcoder.com/practice/ff05d44dfdb04e1d83bdbdab320efbcb?tpId=13&tqId=11211&tPage=3&rp=3&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking) 題目描述：請實現一個函數，用來判斷一顆二叉樹是不是對稱的。注意，如果一個二叉樹同此二叉樹的鏡像是同樣的，定義其為對稱的。 解題思路：如果二叉樹是對稱的，左子樹的左子樹和右子樹的右子樹相同，左子樹的右子樹和右子樹的左子樹相同即可 ``` function isSymmetrical(pRoot) { if(pRoot==null){ return true; } return jury(pRoot,pRoot); } function jury(root1,root2){ if(root1==null && root2==null){ return true; } if((root1==null && root2!=null)||(root1!=null && root2==null)){ return false; } if(root1.val!==root2.val){ return false; } return(jury(root1.left,root2.right)&&jury(root2.left,root1.right)); } ``` # 10.按之字形順序打印二叉樹 [牛客網鏈接](https://www.nowcoder.com/practice/91b69814117f4e8097390d107d2efbe0?tpId=13&tqId=11212&tPage=3&rp=3&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking) 題目描述：請實現一個函數按照之字形打印二叉樹，即第一行按照從左到右的順序打印，第二層按照從右至左的順序打印，第三行按照從左到右的順序打印，其他行以此類推。 ``` function Print(pRoot) { // write code here // 奇數行從左往右，偶數行從右往左 const res = [], queue = [] let level = 1 if (pRoot === null) return res queue.push(pRoot) while (queue.length !== 0) { // 每輪彈出一層的結點并放入下一層的 let low = 0, high = queue.length // 確定每層的結點數 const line = [] while (low++ < high) { let tmp = queue.shift() line.push(tmp.val) if (tmp.left !== null) { queue.push(tmp.left) } if (tmp.right !== null) { queue.push(tmp.right) } } if (level % 2 === 0) { res.push(line.reverse()) } else { res.push(line) } level++ } return res } ``` # 遞歸篇 一棵樹要么是空樹，要么有兩個指針，每個指針指向一棵樹。樹是一種遞歸結構，很多樹的問題可以使用遞歸來處理。 ## 1、樹的高度 [104\. Maximum Depth of Binary Tree (Easy)](https://leetcode.com/problems/maximum-depth-of-binary-tree/description/) ```js /** * @param {TreeNode} root * @return {number} */ var maxDepth = function(root) { if (root === null) return 0 return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1 }; ``` ## 2、平衡樹 [110\. Balanced Binary Tree (Easy)](https://leetcode.com/problems/balanced-binary-tree/description/) ```html 3 / \ 9 20 / \ 15 7 ``` 平衡樹左右子樹高度差都小于等于 1 ```js var isBalanced = function(root) { if (root === null) return true let left = depth(root.left) let right = depth(root.right) return Math.abs(left - right) <= 1 && isBalanced(root.left) && isBalanced(root.right) }; function depth (root) { if (root === null) return 0 let l = depth(root.left) let r = depth(root.right) return Math.max(l, r) + 1 } ``` ## 3.兩節點的最長路徑 [543\. Diameter of Binary Tree (Easy)](https://leetcode.com/problems/diameter-of-binary-tree/description/) ``` Input: 1 / \ 2 3 / \ 4 5 Return 3, which is the length of the path [4,2,1,3] or [5,2,1,3]. ``` ```js var diameterOfBinaryTree = function(root) { let max = 0 maxDepth(root) function maxDepth (root) { if (root === null) return 0 let left = maxDepth(root.left) let right = maxDepth(root.right) max = Math.max(max, left + right) // 這一步很關鍵 return Math.max(left, right) + 1 } return max }; ``` ## 翻轉樹 [226\. Invert Binary Tree (Easy)](https://leetcode.com/problems/invert-binary-tree/description/) ```js var invertTree = function(root) { if (root === null) return null let left = root.left root.left = invertTree(root.right) root.right = invertTree(left) return root }; ``` ## 歸并兩棵樹 [617\. Merge Two Binary Trees (Easy)](https://leetcode.com/problems/merge-two-binary-trees/description/) ```js Input: Tree 1 Tree 2 1 2 / \ / \ 3 2 1 3 / \ \ 5 4 7 Output: 3 / \ 4 5 / \ \ 5 4 7 ``` ```js var mergeTrees = function(t1, t2) { if (t1 === null && t2 === null) return null if (t1 === null) return t2 if (t2 === null) return t1 let root = new TreeNode(t1.val + t2.val) root.left = mergeTrees(t1.left, t2.left) root.right = mergeTrees(t1.right, t2.right) return root }; ``` ## 判斷路徑和是否等于一個數 [Leetcdoe : 112. Path Sum (Easy)](https://leetcode.com/problems/path-sum/description/) ```js Given the below binary tree and sum = 22, 5 / \ 4 8 / / \ 11 13 4 / \ \ 7 2 1 return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22. ``` ```js var hasPathSum = function(root, sum) { if (root === null) return false if (root.left === null && root.right === null && root.val === sum) return true // 葉子結點 return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val) }; ``` ## 統計路徑和等于一個數的路徑數量 [437\. Path Sum III (Easy)](https://leetcode.com/problems/path-sum-iii/description/) ```js root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8 10 / \ 5 -3 / \ \ 3 2 11 / \ \ 3 -2 1 Return 3. The paths that sum to 8 are: 1. 5 -> 3 2. 5 -> 2 -> 1 3. -3 -> 11 ``` 路徑不一定以 root 開頭，也不一定以 leaf 結尾，但是必須連續。 ```js // pathSum：給他一個節點和一個目標值，他返回以這個節點為根的樹中，和為目標值的路徑總數。 ## 子樹 [572\. Subtree of Another Tree (Easy)](https://leetcode.com/problems/subtree-of-another-tree/description/) ```js // 判斷 t 是否為 s 的子樹 var isSubtree = function(s, t) { if (s === null) return false return isSubtreeWithRoot(s, t) || isSubtree(s.left, t) || isSubtree(s.right, t) }; // 判斷以節點 t 為根結點其是否與 s 具有相同的結果 function isSubtreeWithRoot(s, t) { if (t === null && s === null) return true if (t === null || s === null) return false if (t.val !== s.val) return false return isSubtreeWithRoot(s.left, t.left) && isSubtreeWithRoot(s.right, t.right) } ```