树的先序中序后序遍历代码,树的先序中序后序遍历

先序遍历

这是先序遍历要求的顺序，我们看看仅仅是遍历这个二叉树，怎么迭代遍历

模板如下：

var Traversal = function(root) {
    const res = [];
  const stack = [];
  while (root || stack.length) {
    while (root) {
      res.push(root.val);
      stack.push(root);
      root = root.left;
    }
    root = stack.pop();
    root = root.right;
  }
  return res;
};

就以上图为例，我们看看这个代码是怎么运行的：

整体压栈的顺序是

• A、B、D入栈，
• D出栈
• B出栈
• E入栈
• E出栈
• A出栈
• C入栈
• C出栈
• F入栈
• F出栈我们把上面入栈的元素按顺序打印就是前序遍历的答案!!!!!

即：

我们可以看到，入栈就是前序遍历要求的顺序，A、B、D、E、C、F

是不是很有意思，下面的中序遍历，我们看看出栈顺序是不是中序遍历的要求：D、B、E、A、C、F

这就是中序遍历的顺序！！！

所以前序和中序遍历我们的代码就出来了：

var preorderTraversal = function(root) {
    // 初始化数据
    const res =[];
    const stack = [];
    while (root || stack.length){
      while(root){
        res.push(root.val);
        stack.push(root);
        root = root.left;
      }
      root = stack.pop();
      root = root.right;
    }
    return res;
};

中序遍历

中序遍历的图如下，代码一起了：

const inorderTraversal = (root) => {
    if(!root) return [];
  const res = [];
  const stack = [];
  while(root || stack.length){
      while(root){
          stack.push(root)
          root = root.left;
      }
     root = stack.pop();
     res.push(root.val);
     root = root.right;
  }
  return res;
};

后序遍历

后序遍历有点不太一样，但是套路是一样的，我们需要先遍历右子树，再遍历左子树，反着来，就可以了，代码如下：

var postorderTraversal = function(root) {
  // 初始化数据
    const res =[];
    const stack = [];
    while (root || stack.length){
      while(root){
        stack.push(root);
        res.unshift(root.val);
        root = root.right;
      }
      root = stack.pop();
      root = root.left;
    }
    return res;
};