leetcode-二叉树-中序遍历

一、模板

1. 递归

/**
 * 递归-通用中序遍历模板
 */

var problem = (root) => {
  // 0. prepare
  const res = []
  dfs(root)
  return res

  function dfs (node, param1, param2) {
    // 1. terminator 终止条件
    if (node === null) {
      // process result
      return
    }

    // 2. drill down 进入下一层
    dfs(node.left, param1, param2)

    // 3. process logic in current level 处理当前层逻辑
    res.push(node.val)

    // 4. drill down 进入下一层
    dfs(node.right, param1, param2)

    // 5. reverse the current level status if needed 清理当前层状态
    // return ...
  }
}

二、题目

94. 二叉树的中序遍历

/**
 * 递归
 */

var inorderTraversal = function(root) {
  const ret = []
  if(root === null) return ret
  inOrder(root)
  return ret

  function inOrder(node){
    if(node === null) return
    inOrder(node.left)
    ret.push(node.val)
    inOrder(node.right)
  }
};

/**
 * 非递归
 */

var inorderTraversal = function(root) {
  const ret = []
  if(root === null) return ret
  const stack = []
  let cur = root
  while(stack.length || cur !== null){
    if(cur !== null ){
      stack.push(cur)
      cur = cur.left
    }else{
      cur = stack.pop()
      ret.push(cur.val)
      cur = cur.right
    }
  }

  return ret
};

/**
 * 非递归——模拟系统栈
 */
class Command {
  constructor(s, node) {
    this.s = s
    this.node = node
  }
}

var inorderTraversal = function(root) {
let res = []
  if (root === null) return res
  const stack = [new Command("go",root)]
  while(stack.length){
    const command = stack.pop()
    if(command.s === 'print')
      res.push(command.node.val)
    else{
      if(command.node.right)
        stack.push(new Command("go",command.node.right))
      stack.push(new Command("print",command.node))
      if(command.node.left)
        stack.push(new Command("go",command.node.left))
    }
  }
  return res
};

98. 验证二叉搜索树

/**
 * 递归
 */
var isValidBST = function (root) {
  return _isValidBST(root,-Infinity,Infinity)

  function _isValidBST(root,lower,upper){
    if(root === null) return true

    if(root.val <= lower || root.val >= upper) return false

    return _isValidBST(root.left,lower,root.val) && _isValidBST(root.right,root.val,upper)
  }
};

/**
 * 递归
 */

var isValidBST = function (root) {
  let prev = -Infinity
  return _isValidBST(root)

  function _isValidBST(root) {
    if (root === null) return true

    if(!_isValidBST(root.left))
      return false
    if(root.val <= prev)
      return false
    prev = root.val

    return _isValidBST(root.right)
  }
};

/**
 * 非递归
 */

var isValidBST = function (root) {
  let stack = []
  let prev = -Infinity
  let cur = root
  while(stack.length || cur !== null){
    if(cur!== null){
      stack.push(cur)
      cur = cur.left
    }else{
      cur = stack.pop()
      if(cur.val <= prev)
        return false
      prev = cur.val
      cur = cur.right
    }
  }
  return true
};