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. drill down 进入下一层
    dfs(node.right, param1, param2)

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

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

二、题目

145. 二叉树的后序遍历

/**
 * 递归
 */

var postorderTraversal = function (root) {
  const ret = []
  if (!root) return ret
  postOrder(root)
  return ret

  function postOrder(node) {
    if (!node) return
    postOrder(node.left)
    postOrder(node.right)
    ret.push(node.val)
  }
};

/**
 * 非递归——2个栈
 */

var postorderTraversal = function (root) {
  const ret = []
  if (!root) return ret
  
  const s1 = [root]
  const s2 = []
  while(s1.length){
    const cur = s1.pop()
    s2.push(cur)
    if(cur.left) s1.push(cur.left)
    if(cur.right) s1.push(cur.right)
  }
  while(s2.length)
    ret.push(s2.pop().val)

  return ret
};

/**
 * 非递归——1个栈
 */

var postorderTraversal = function (root) {
  const ret = []
  if (!root) return ret
  
  const s1 = [root]
  let h = root,
      cur
  while(s1.length){
    cur = s1[s1.length-1]
    if(cur.left && h !== cur.left && h !== cur.right)
      s1.push(cur.left)
    else if( cur.right && h !== cur.right)
      s1.push(cur.right)
    else{
      ret.push(s1.pop().val)
      h = cur
    }
  }

  return ret
};


/**
 * 非递归——模拟系统栈
 */

class Command {
  constructor(s, node) {
    this.s = s
    this.node = node
  }
}

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

590. N叉树的后序遍历

/**
 * 递归
 */

var postorder = function (root) {
  const ret = []
  if (!root) return ret
  _postorder(root)
  return ret

  function _postorder(node) {
    if (!node) return
    for (let i = 0; i < node.children.length; i++) {
      _postorder(node.children[i])
    }
    ret.push(node.val)
  }
};

/**
 * 非递归
 */

var postorder = function (root) {
  const ret = []
  if (!root) return ret
  let stack1 = [root]
  let stack2 = []
  while(stack1.length){
    const cur = stack1.pop()
    stack2.push(cur)
    for (let i = 0; i < cur.children.length; i++) {
      stack1.push(cur.children[i])
    }
  }
  while(stack2.length)
    ret.push(stack2.pop().val)
  return ret
};

104. 二叉树的最大深度

var maxDepth = function (root) {
  if (root === null) return 0

  let leftMaxDepth = maxDepth(root.left)
  let rightMaxDepth = maxDepth(root.right)
  return Math.max(leftMaxDepth, rightMaxDepth) + 1
}

111. 二叉树的最小深度

var minDepth = function (root) {
  if (!root) return 0
  if (root.left === null && root.right === null) return 1

  let res = Number.MAX_SAFE_INTEGER
  if (root.left) res = Math.min(minDepth(root.left), res)
  if (root.right) res = Math.min(minDepth(root.right), res)
  return res + 1
}

559. N 叉树的最大深度

var maxDepth = function(root) {
    if(!root) return 0
  	if(root.children.length === 0) return 1
    let max = 0
    for(let i = 0;i<root.children.length;i++)
      max = Math.max(max,maxDepth(root.children[i]))
    return max+1
};

226. 翻转二叉树

var invertTree = function (root) {
  if (root === null) return null

  let left = invertTree(root.left)
  let right = invertTree(root.right)
  root.left = right
  root.right = left
  return root
}

100. 相同的树

/**
 * 递归
 */

var isSameTree = function(p, q) {
    if(p === null && q === null) return true
    else if(p === null || q === null || p.val !== q.val) return false

    return isSameTree(p.left,q.left) && isSameTree(p.right,q.right)
};

/**
 * 非递归
 */

var isSameTree = function(p, q) {
    if(p === null && q === null ) return true
    if(p === null || q === null || p.val !== q.val) return false
    const q1=  [p]
    const q2 = [q]
    while(q1.length && q2.length){
      const cur1 = q1.shift()
      const cur2 = q2.shift()
      if(cur1.val !== cur2.val) return false

      if(cur1.left === null && cur2.left === null){}
      else if(!cur1.left || !cur2.left) return false
      else {
        q1.push(cur1.left)
        q2.push(cur2.left)
      }

      if(cur1.right === null && cur2.right === null){}
      else if(!cur1.right || !cur2.right) return false
      else {
        q1.push(cur1.right)
        q2.push(cur2.right)
      }
    }
    return true
};