关于javascript:二叉树遍历方法总结

深度优先遍历

1) 前序遍历

递归实现：

const preOrder = (root) => {
  let result = [];
  const traverseNode = (node) => {
    if (node) {
      // 先根节点
      result.push(node.val);
      // 而后遍历左子树
      traverseNode(node.left);
      // 再遍历右子树
      traverseNode(node.right);
    }
  }
  traverseNode(root);
  return result;
}

非递归实现：

const preOrder = (root) => {
  let list = [];
  let stack = [];
  // 当根节点不为空的时候，将根节点入栈
  if (root != null) stack.push(root);
  while (stack.length > 0) {
    root = stack.pop();
    // 先拜访根节点
    list.push(root.val);
    // 咱们先打印左子树，而后右子树
    // 所以先入栈的是右子树，而后左子树
    if (root.right != null) stack.push(root.right);
    if (root.left != null) stack.push(root.left);
  }
  return list;
}

2) 中序遍历

递归实现：

const inOrder = (root) => {
  let result = [];
  const traverseNode = (node) => {
    if (node) {
      // 先遍历左子树
      traverseNode(node.left);
      // 而后根节点
      result.push(node.val);
      // 再遍历右子树
      traverseNode(node.right);
    }
  }
  traverseNode(root);
  return result;
}

非递归实现：

const inOrder = (root) => {
  let list = [];
  let stack = [];
  while (stack.length > 0 || root != null) {
    if (root != null) {
      // 如果以后节点非空，就将以后节点入栈
      stack.push(root);
      // 指针向以后节点的左节点方向挪动
      root = root.left;
    } else {
      // 以后节点为空，则从栈顶弹出元素
      root = stack.pop();
      list.push(root.val);
      // 指针向右节点方向挪动
      root = root.right;
    }
  }
  return list;
}

3) 后序遍历

递归实现：

const postOrder = (root) => {
  let result = [];
  const traverseNode = (node) => {
    if (node) {
      // 先遍历左子树
      traverseNode(node.left);
      // 而后遍历右子树
      traverseNode(node.right);
      // 最初根节点
      result.push(node.val);
    }
  }
  traverseNode(root);
  return result;
}

非递归实现：

const postOrder = (root) => {
  let list = [];
  let stack = [];
  // 当根节点不为空，将根节点入栈
  if (root != null) stack.push(root);
  while (stack.length > 0) {
    root = stack.pop();
    // 因为后序遍历输入程序是：左=>右=>根
    // 先将增加后果的程序反一下
    list.unshift(root.val);
    // 而后让左子树先入栈，后右子树
    // 这样出栈程序就变成先右后左
    if (root.left != null) stack.push(root.left);
    if (root.right != null) stack.push(root.right);
  }
  return list;
}