js+树

最近要开始找工作啦，很久很久之前用python和java刷过刷数据结构和算法，现在已经记忆模糊了。而且从来没有用js实现过，这次就用js刷一遍好了。

二叉树

首先定义树的节点，包含数据域和后驱指针

function TreeNode(val){
  this.val = val
  this.left = this.right = null
}

然后定义树，树在初始化时应当定义其根节点

function BinaryTree(root){
  this.root = root
}

树的遍历

树的遍历常见的有四种，包括先序遍历，中序遍历，后序遍历。
先序遍历的意思就是先处理当前节点，再处理当前节点的左右子树

BinaryTree.prototype.preorder = function(){
  ans = []
  function helper(node){
    if(node){
      ans.push(node.val)
      helper(node.left)
      helper(node.right)
    }
  }
  helper(this.root)
  return ans
}

同理，我们也可以很容易的写出，中序遍历和后序遍历

BinaryTree.prototype.inorder = function(){
  ans = []
  function helper(node){
    if(node){
      helper(node.left)
      ans.push(node.val)
      helper(node.right)
    }
  }
  helper(this.root)
  return ans
}

BinaryTree.prototype.postorder = function(){
  ans = []
  function helper(node){
    if(node){
      helper(node.left)
      helper(node.right)
      ans.push(node.val)
    }
  }
  helper(this.root)
  return ans
}

层序遍历稍微复杂一点，需要用一个队列来辅助，思路就是先把根节点遍历，然后把根节点的子节点放入待遍历层这（队列），然后不断处理和更新这个队列直到其为空

BinaryTree.prototype.levelorder = function(){
  var level = [this.root]
  var ans = []
  var tmp
  while(level.length > 0){
    ans = ans.concat(level.map((node) => node.val))
    tmp = []
    level.forEach((node) => {
      if(node.left) tmp.push(node.left)
      if(node.right) tmp.push(node.right)
    })
    level = tmp
  }
  return ans
}

树的高度

递归调用就好啦

BinaryTree.prototype.getHeight = function(node){
  if(typeof node === 'undefined') node = this.root
  if (!node) return 0
  return Math.max(this.getHeight(node.left), this.getHeight(node.right)) + 1
}

树的 最大/最小 深度

BinaryTree.prototype.maxDepth = function(node){
  if (typeof node === 'undefined') node = this.root
  if(node){
    return Math.max(this.maxDepth(node.left), this.maxDepth(node.right)) + 1
  }
  return 0
}

BinaryTree.prototype.minDepth = function(node){
  if (typeof node === 'undefined') node = this.root
  if (!node) return 0
  if (!node.left || !node.right){
    return this.minDepth(node.left) + this.minDepth(node.right) + 1
  }
  return Math.min(this.minDepth(node.left), this.minDepth(node.right)) + 1
}

判断两棵树是否相同

function isSameTree(p,q){
  if(!p || !q) return p === q
  return p.val === q.val && isSameTree(p.left, q.left) && isSameTree(p.right, q.right)
}

判断一棵树是否平衡

//Balanced ?
BinaryTree.prototype.isBalanced = function(node){
  if(typeof node === 'undefined') node = this.root
  if(!node) return true
  return Math.abs(this.getHeight(node.left) - this.getHeight(node.right)) < 2 && this.isBalanced(node.left) && this.isBalanced(node.right)
}