leetcode-二叉树-前序遍历

一、模板

1. 递归

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

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

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

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

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

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

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

二、题目

144. 二叉树的前序遍历

/**
 * 递归
 */

var preorderTraversal = function (root) {
  const ret = []
  if(root === null) return ret
  preorder(root)
  return ret

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

/**
 * 非递归
 */

var preorderTraversal = function (root) {
  const ret = []
  if(root === null) return ret
  const stack = [root]
  while(stack.length){
    const cur = stack.pop()
    if(cur){
      ret.push(cur.val)
      stack.push(cur.right)
      stack.push(cur.left)
    }
  }
  return ret
};


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

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

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

589. N叉树的前序遍历

/**
 * 递归
 */

var preorder = function(root) {
  const ret = []
  if(root === null) return ret
  _preorder(root)     
  return ret

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

/**
 * 非递归
 */

var preorder = function(root) {
  const ret = []
  if(root === null) return ret
  const stack = [root]
  while(stack.length){
    const cur = stack.pop()
    ret.push(cur.val)
    for(let i = cur.children.length - 1;i >= 0;i--){
      stack.push(cur.children[i])
    }
  }
  return ret
};

112. 路径总和

var hasPathSum = function (root, sum) {
  if(root === null) 
    return false
    
  if(root.left === null && root.right === null) 
    return root.val === sum
  
  return hasPathSum(root.left,sum-root.val) || hasPathSum(root.right, sum-root.val)
}

257. 二叉树的所有路径

var binaryTreePaths = function (root) {
  let res = []
  buildPaths(root,"")
  return res

  function buildPaths(root,s){
    if(root === null) return 
    if(root.left === null && root.right === null){
      s+=root.val
      res.push(s)
      return 
    }

    buildPaths(root.left,s+root.val+"->")
    buildPaths(root.right,s+root.val+"->")
  }
}

/**
 * 当前函数递归
 */

var binaryTreePaths = function (root) {
  let res = []

  if (root === null) return res
  if (root.left === null && root.right === null) {
    res.push(root.val + "")
    return res
  }

  let leftS = binaryTreePaths(root.left)
  let rightS = binaryTreePaths(root.right)
  
  for (let i = 0; i < leftS.length; i++) 
    res.push(root.val + "->" + leftS[i])
  for (let i = 0; i < rightS.length; i++) 
    res.push(root.val + "->" + rightS[i])

  return res
}

437. 路径总和 III

var pathSum = function (root, sum) {
  let res = 0
  if (root === null) return res
  res = findPath(root, sum)
  res += pathSum(root.left, sum)
  res += pathSum(root.right, sum)
  return res

  function findPath(root, sum) {
    if (root === null) return 0
    let res = 0
    if (root.val === sum)
      res += 1

    res += findPath(root.left, sum - root.val)
    res += findPath(root.right, sum - root.val)

    return res
  }
};