Js算法與資料結構拾萃（4）：二叉樹
根據著名開源軟體homebrew作者Max Howell自己的描述，他去Google面試，遇到二叉樹鏡像翻轉這題，沒寫出來。最後被拒了。
是以隻要答對這道題，你就可以超越世界級大牛，問鼎碼林之巅（逃）
導讀：
•二叉樹知識重點•二叉樹深度不一，是以天生适用遞歸，是以可用遞歸處理•判斷兩樹相等•翻轉二叉樹•二叉樹三種深度周遊（疊代）•前序周遊•中序周遊•後序周遊•二叉樹的一些疊代特性•判斷是否二叉搜尋樹•二叉搜尋樹的最近公共祖先•二叉樹的最近公共祖先
補白
準備閱讀：
•《javascript資料結構和算法》讀書筆記（6）：樹[1]• 自平衡樹[2]
本文是對此知識點的複習和擴充。
樹的邏輯是和連結清單高度相似的。本文中樹指的是二叉樹，而二叉樹還有二叉搜尋樹（BST），紅黑樹，“B樹”（B Tree）等。同時需要掌握的還有周遊方法（前序周遊，中序周遊，後序周遊）等。它們的共同特點在于遞歸和疊代。
正常來說，用js實作Bst二叉搜尋樹，需要借鑒連結清單的思路，一個樹的節點包括左子樹left，右子樹right 和它本身的值。
•定義Node生成的工廠方法。•插入：定義插入邏輯•周遊（敲黑闆劃重點）：•中序周遊：左子樹->根節點->右子樹，如果是BST的周遊順序：是由小到大。•前序周遊：根節點->左子樹->右子樹•後序周遊：左子樹->右子樹->根節點•搜尋：簡便起見，用周遊方法搜尋即可•最大最小方法，max（不斷檢索右側），min（不斷檢索左側）•移除節點(delete)•找到要移除的節點
_root
，它的子節點（
_root.left
/
_root.right
）和它的父節點
parentNode
以及
_root
相對于父節點的對應位置
side
，這也是遞歸終止的條件•對
_root
做判斷：•
_root
沒有子節點，則
parentNode
直接設為null•
_root
有一個子節點，則跳過root，把父節點的對應側的指針直接指向子節點。•如果
_root
包括兩個子節點：找到
_root
右子樹的最小節點
const node=min(_root.right)
，令它替換掉
_root
：
remove(node，_root.right)node.right=_root.right
，
node.left=_root.leftparentNode[side]=node
接下來看怎麼實作:
class BinarySearchTree {
constructor() {
this.Node = function (key) {
this.key = key;
this.left = null;
this.right = null;
}
this.root = null;
}
// 插入節點
insert(key) {
// 定義插入邏輯
const insertNode = (_root, _node) => {
if (_root.key > _node.key) {
if (_root.left == null) {
_root.left = _node;
} else {
insertNode(_root.left, _node);
}
} else {
if (_root.right == null) {
_root.right = _node;
} else {
insertNode(_root.right, _node);
}
}
}
const node = new this.Node(key);
if (this.root == null) {
this.root = node;
} else {
insertNode(this.root, node)
}
}
// 中序周遊
inOrderTraverse(callback) {
const inOrderTraverse = (_root, _callback = () => { }) => {
// 頂層開始
if (_root !== null) {
// 左子樹->根節點->右子樹
inOrderTraverse(_root.left, _callback);
_callback(_root.key);
inOrderTraverse(_root.right, _callback);
}
}
inOrderTraverse(this.root, callback);
}
// 先序周遊
preOrderTraverse(callback) {
const preOrderTraverse = (_root, callback) => {
if (_root !== null) {
// 根節點->左子樹->右子樹
_callback(_root.key);
preOrderTraverse(_root.left, _callback);
preOrderTraverse(_root.right, _callback);
}
}
preOrderTraverse(this.root, callback);
}
// 後序周遊
postOderTraverse(callback) {
const postOderTraverse = (_root, _callback) => {
// 左子樹->右子樹->根節點
postOderTraverse(_root.left, _callback);
postOderTraverse(_root.right, _callback);
callback(_root.key);
}
}
// 搜尋特定值
search(key) {
// 周遊即可
let flag = false;
this.inOrderTraverse((_key) => {
if (_key == key) {
flag = true;
}
})
return flag;
}
// 查找最大最小值
find(_root, side) {
if (!_root, side) {
if (!_root[side]) {
return _root;
} else {
return this.find(_root[side], side)
}
}
}
// 最大值，不斷查找右側
max() {
return this.find(this.root, 'right');
}
// 最小值，不斷查找左側
min() {
return this.find(this.root, 'left');
}
// 移除節點
_remove(_node, _key, parentNode, side) {
if (_key < _node.key) {
return this._remove(_node.left, _key, _node, 'left');
} else if (_key > _node.key) {
return this._remove(_node.right, _key, _node, 'right');
} else if (_node.key = _key) {
// 找到了節點
if (!parentNode) {
this.root = null;
return this.root;
} else {
if (!_node.left && !_node.right) {
parentNode[side] = null;
} else if (_node.left && !_node.right) {
let tmp = _node.left;
parentNode[side] = tmp;
} else if (_node.left && _node.right) {
let tmpR = _node.right;
let tmpL = _node.left;
let node = this.find(tmpR, 'left');
this._remove(tmpR, node.key);
node.left = tmpL;
node.right = tmpR;
parentNode[side] = node;
}
return this.root;
}
}
}
remove(key) {
if (this.search(key)) {
return this._remove(this.root, key);
} else {
throw new Error('找不到key');
}
}
}
// 測試用例
const a = new BinarySearchTree();
const list = [11, 7, 15, 5, 3, 9, 8, 10, 13, 12, 14, 20, 18, 25]
for (let i = 0; i < list.length; i++) {
a.insert(list[i]);
}
a.inOrderTraverse(key => {
console.log(key)
})
a.remove(7)
console.log('------------')
a.inOrderTraverse(key => {
console.log(key)
}) 複制
接下來就看下樹在算法中的實踐。
【案例1】Same Tree 相同的樹
對應leetcode第100題 難度：簡單
https://leetcode.com/problems/same-tree/
Given two binary trees, write a function to check if they are the same or not.
Two binary trees are considered the same if they are structurally identical and the nodes have the same value.
給定兩個二叉樹，編寫一個函數來檢驗它們是否相同。
如果兩個樹在結構上相同，并且節點具有相同的值，則認為它們是相同的。
題解:遞歸判斷
這種題還是比較簡單，注意測試用例可能包含null的情況。
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} p
* @param {TreeNode} q
* @return {boolean}
*/
var isSameTree = function(p, q) {
if(p==null && q==null){
return true
}
if(p!=null && q!=null && p.val==q.val){
return isSameTree(p.left,q.left) && isSameTree(p.right,q.right)
}else{
return false;
}
}; 複制
效率一般：
【案例2】 Invert Binary Tree 翻轉二叉樹
對應leetcode第226題 難度：簡單
https://leetcode.com/problems/invert-binary-tree/
invert a binary tree.
Example:
Input:
4
/ \
2 7
/ \ / \
1 3 6 9 複制
Output:
4
/ \
7 2
/ \ / \
9 6 3 1 複制
題解：遞歸
這題也是遞歸，沒啥好說的。
/**
* 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) {
if(root!==null){
let tmp=root.left;
root.left=root.right;
root.right=tmp;
invertTree(root.left);
invertTree(root.right);
}
return root
}; 複制
樹天生适合遞歸，但凡是遞歸都可以轉化為循環疊代。
【案例3】二叉樹周遊3題
知道了三種周遊邏輯，我們可以開始打包做三道題
3.1 前序周遊
對應leetcode第144題 難度：中等
https://leetcode.com/problems/binary-tree-preorder-traversal/
Given a binary tree, return the preorder traversal of its nodes' values.
Example:
Input: [1,null,2,3]
1
\
2
/
3
Output: [1,2,3] 複制
Follow up: Recursive solution is trivial, could you do it iteratively?
進階: 遞歸算法很簡單，你可以通過疊代算法完成嗎？
題解1 遞歸
遞歸可以考慮加個回調：
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {number[]}
*/
var preorderTraversal = function(root,callback) {
let ret=[]
if(!callback){
callback=(val)=>{
ret.push(val);
}
}
if(root!=null){
// 在此處，隻需要調整周遊邏輯，即可完成前中後的周遊解法
ret.push(root.val);
let l=preorderTraversal(root.left,callback);
let r=preorderTraversal(root.right,callback);
ret=ret.concat(l);
ret=ret.concat(r);
}
return ret;
}; 複制
題解2：疊代
再看疊代方法。
var preorderTraversal = function(root) {
let ret=[];
if (root != null){
let stack = [root];
while(stack.length) {
// 每次彈棧處理
let { left, right, val } = stack.pop()
ret.push(val)
right && stack.push(right) // 先把right存入棧中
left && stack.push(left)
}
}
return ret;
} 複制
3.2 中序周遊
對應leetcode第94題 難度：中等
https://leetcode.com/problems/binary-tree-inorder-traversal/
疊代題解
注意周遊的順序
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {number[]}
*/
var inorderTraversal = function(root) {
let ret=[];
if (root != null){
let stack = [];
let cur=root;
while(stack.length||cur!=null) {
// 先不斷将左側入棧，直到左側子樹為null，然後将彈出棧頂，push到ret中。
if(cur){
stack.push(cur);
cur=cur.left;
}else{
cur=stack.pop();
ret.push(cur.val);
cur=cur.right;
}
}
return ret
}
return ret;
}; 複制
3.3 後序周遊
對應leetcode 145題 難度：困難
https://leetcode.com/problems/binary-tree-postorder-traversal/
疊代題解
實際上隻要掌握了中序周遊的邏輯，都好說。後序周遊需要一個緩存指針r來判斷是否把左側都周遊完了。
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {number[]}
*/
var postorderTraversal = function(root) {
let ret=[];
let r=null;
if (root != null){
let stack = [];
let cur=root;
while(stack.length||cur!=null) {
if(cur){
stack.push(cur);
cur=cur.left;
}else{
cur=stack[stack.length-1];
if(cur.right==null||cur.right==r){
ret.push(cur.val);
r=cur;
stack.pop();
cur=null;
}else{
cur=cur.right;
}
}
}
}
return ret;
}; 複制
運作效率，差強人意吧。
【案例4】 Validate Binary Search Tree 驗證二叉搜尋樹（BST）
對應leetcode第98題 難度：中等
https://leetcode.com/problems/validate-binary-search-tree/
Given a binary tree, determine if it is a valid binary search tree (BST).
Assume a BST is defined as follows:
•The left subtree of a node contains only nodes with keys less than the node's key.•The right subtree of a node contains only nodes with keys greater than the node's key.•Both the left and right subtrees must also be binary search trees.
再補白部分的文章中，專門證明了：對于BST，中序周遊的結果是遞增的。
也就是說你把中序周遊的過程做多一個判斷，就可以得出結果。
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {boolean}
*/
var isValidBST = function(root) {
let ret=[];
if (root != null){
let stack = [];
let cur=root;
while(stack.length||cur!=null) {
if(cur){
stack.push(cur);
cur=cur.left;
}else{
cur=stack.pop();
if(ret.length){
if(ret[ret.length-1]>=cur.val){
return false;
}
}
ret.push(cur.val);
cur=cur.right;
}
}
}
return true;
}; 複制
【案例5】 Maximum Depth of Binary Tree 二叉樹的最大深度
對應leetcode 104題 難度：簡單
https://leetcode.com/problems/maximum-depth-of-binary-tree/
Given a binary tree, find its maximum depth.
The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.
給定一個二叉樹，找出其最大深度。
二叉樹的深度為根節點到最遠葉子節點的最長路徑上的節點數。
Note: A leaf is a node with no children.
說明: 葉子節點是指沒有子節點的節點。
Example:
Given binary tree
[3,9,20,null,null,15,7]
,
3
/ \
9 20
/ \
15 7 複制
return its depth = 3.
題解：遞歸
網上有所謂“一行”搞定的解法。思路就是，遞歸比較樹的兩個節點長度最大值，
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {number}
*/
var maxDepth = function(root) {
return root == null ? 0 : Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
}; 複制
【案例6】Lowest Common Ancestor of a Binary Search Tree 二叉搜尋樹的最近公共祖先
對應leetcode 235題 難度：簡單
https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-search-tree/
Given a binary search tree (BST), find the lowest common ancestor (LCA) of two given nodes in the BST.
According to the definition of LCA on Wikipedia[3]: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”
Given binary search tree: root = [6,2,8,0,4,7,9,null,null,3,5]
給定一個二叉搜尋樹, 找到該樹中兩個指定節點的最近公共祖先。
百度百科中最近公共祖先的定義為：“對于有根樹 T 的兩個結點 p、q，最近公共祖先表示為一個結點 x，滿足 x 是 p、q 的祖先且 x 的深度盡可能大（一個節點也可以是它自己的祖先）。”
例如，給定如下二叉搜尋樹: root = [6,2,8,0,4,7,9,null,null,3,5]
img
Example 1:
Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
Output: 6
Explanation: The LCA of nodes 2 and 8 is 6. 複制
Example 2:
Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
Output: 2
Explanation: The LCA of nodes 2 and 4 is 2, since a node can be a descendant of itself according to the LCA definition. 複制
Note:
•All of the nodes' values will be unique.•p and q are different and both values will exist in the BST.
題解：遞歸
利用二叉搜尋樹的特點，如果p、q的值都小于root，說明p q 肯定在root的左子樹中；如果p q都大于root，說明肯定在root的右子樹中，如果一個在左一個在右 則說明此時的root記為對應的最近公共祖先。
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @param {TreeNode} p
* @param {TreeNode} q
* @return {TreeNode}
*/
var lowestCommonAncestor = function(root, p, q) {
if(p.val<root.val && q.val<root.val){
return lowestCommonAncestor(root.left,p,q);
}
if(p.val>root.val && q.val>root.val){
return lowestCommonAncestor(root.right,p,q);
}
return root
}; 複制
【案例7】二叉樹的最近公共祖先
對應leetcode 236題 難度：中等
https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/
給定一個二叉樹, 找到該樹中兩個指定節點的最近公共祖先。和案例6唯一的不同在于，此題不限定BST。是以不能用BST的特性取巧了。
題解：遞歸
思路是很明确的，寫一個查詢方法search來判斷兩個樹是否存在包含關系。然後不斷判斷
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @param {TreeNode} p
* @param {TreeNode} q
* @return {TreeNode}
*/
var lowestCommonAncestor = function(root, p, q) {
// 查詢方法：判斷後者是否在前者當中檢索到
const search=(_p,_q)=>{
if(_p!=null){
if(_p!=null && _q!=null && _p.val==_q.val){
return true;
}else{
return search(_p.left,_q)||search(_p.right,_q);
}
}
return false;
}
// 從上往下找：是否滿足條件，能滿足則傳回。
if(root!=null){
let ret=lowestCommonAncestor(root.left,p,q)||lowestCommonAncestor(root.right,p,q);
if(search(root,p) && search(root,q)){
return ret?ret:root;
}else{
return ret
}
}
return root;
}; 複制
這種代碼送出的性能開銷是驚人的，因為search的緣故
其實還有更簡單的寫法。
注意p, q必然存在樹内, 且所有節點的值唯一。
遞歸思想, 對以root為根的(子)樹進行查找p和q, 如果root == null || p || q 直接傳回root
表示對于目前樹的查找已經完畢, 否則對左右子樹進行查找, 根據左右子樹的傳回值判斷:
1.左右子樹的傳回值都不為null, 由于值唯一左右子樹的傳回值就是p和q, 此時root為LCA2.如果左右子樹傳回值隻有一個不為null, 說明隻有p和q存在與左或右子樹中, 最先找到的那個節點為LCA3.左右子樹傳回值均為null, p和q均不在樹中, 傳回null
var lowestCommonAncestor = function (root, p, q) {
if (root == null || p == root || q == root){
return root;
};
const left = lowestCommonAncestor(root.left, p, q);
const right = lowestCommonAncestor(root.right, p, q);
if (left == null) return right;
if (right == null) return left;
return root;
}; 複制
性能相對好些：
References
[1]
《javascript資料結構和算法》讀書筆記（6）：樹: http://mp.weixin.qq.com/s?__biz=MzIxMDQ2NjUwNg==&mid=2247483830&idx=1&sn=7e9d20a4cc178c0fc796e5f90fec74c9&chksm=97656213a012eb05b3627bda5045cf26f662d1500cc85b80c6f9f025898b9d4a6d3b7572ddb9&token=1402742408&lang=zh_CN#rd
[2]
自平衡樹: http://mp.weixin.qq.com/s?__biz=MzIxMDQ2NjUwNg==&mid=2247483834&idx=1&sn=b1889e5939f33d230bccc302be141aa0&chksm=9765621fa012eb09f0462df622fbb0a134737339e2bb1d3b9d44bc71e1211aea8908965373d8&token=1402742408&lang=zh_CN#rd
[3]
definition of LCA on Wikipedia: https://en.wikipedia.org/wiki/Lowest_common_ancestor