【数据结构分类】二叉树-概览 about mini-vue HOT 2 OPEN

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */

// BFS 解法一
var preorderTraversal = function (root) {
  if (!root) return []

  const ans = []
  const stack = [root]

  while (stack.length) {
    const { val, left, right } = stack.pop()

    ans.push(val) // 处理当前节点
    if (right) stack.push(right) // 先右
    if (left) stack.push(left) // 后左
  }

  return ans
}

/* ------------------------------------------------ 分割线----------------------------------------------------- */

// BFS 解法二
var preorderTraversal = function (root) {
  if (!root) return []

  const ans = []
  const stack = [root]
  while (stack.length) {
    let curr = stack.pop()
    while (curr) {
      ans.push(curr.val)
      if (curr.right) stack.push(curr.right) // push右子节点
      curr = curr.left // 将指针指向左子节点
    }
  }

  return ans
}

// 了解到层序遍历的顺序之后，我们就可以通过循环利用指针的特性逐步推送到下一层
// 此方法在in-order和post-order的实现中较常用到

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var inorderTraversal = function (root) {
  const stack = []
  const ans = []

  while (root || stack.length) {
    while (root) {
      stack.push(root)
      root = root.left
    }

    root = stack.pop()
    ans.push(root.val)
    root = root.right
  }

  return ans
}

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */

// BFS
var postorderTraversal = function (root) {
  if (!root) return []

  const stack = []
  const ans = []
  let curr = root

  while (stack.length || curr) {
    if (curr) {
      ans.push(curr.val)
      stack.push(curr) // 储存节点
      curr = curr.right // 每次先遍历右节点，再遍历左节点
    } else {
      const node = stack.pop() // 右子树走到底之后，再从获取已经遍历过右子树的中间结果，将它出栈，并遍历它的左子树
      curr = node.left
    }
  }

  return ans.reverse()
}

var preorderTraversal = function (root) {
  if(!root) return []
  const ans = []
  const stack = [root]
  while(stack.length) {
    const {val,left,right} = stack.pop()
    ans.push(val)
    if(right) stack.push(right)
    if(left) stack.push(left)
  }
  return ans
}

// DFS 直接套用模板即可
var preorderTraversal = function (root) {
  return getTree(root)
}

const getTree = (node, arr = []) => {
  if (!node) return arr

  arr.push(node.val) // 处理当前节点
  getTree(node.left, arr)
  getTree(node.right, arr)

  return arr
}