Js算法与数据结构拾萃（4）：二叉树

2020 年 2 月 25 日
笔记

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