二叉树的遍历

现在决定把自己很久以前的一些文章重新markdown一下，发到简书来，先从这篇二叉树的遍历说起的。
大家都知道二叉树的遍历分为前序遍历，中序遍历，后序遍历。记得大学学习这一部分的时候，觉得用递归就可以轻易实现，简直太简单了，所以也就没有认真学，不过后来面试的时候考官要写一下二叉树的中序遍历，而且不能用递归，当时就很尴尬了，所以现在把二叉树的每种遍历思想和方法都记录一下，做个备忘

递归的解法来解决前序中序和后续的遍历

这简直是太简单不过了

递归前序遍历

public static void preTranverse(TreeNode root){
  if(root != null){
    visit(root);
    preTranverse(root.leftChild);
    preTranverse(root.rightChild);
  }
}

是不是非常言简意赅，遍历的时候先访问本身，然后遍历左节点，接着遍历右节点，而且简单易懂，接下来直接写中序遍历和后续遍历，思路是一样的

递归中序遍历

public static void midTranverse(TreeNode root){
  if(root != null){
    midTranverse(root.leftChild);
    visit(root);
    midTranverse(root.rightChild);
  }
}

递归后续遍历

public static void postTranverse(TreeNode root){
  if(root != null){
    postTranverse(root.leftChild);
    postTranverse(root.rightChild);
    visit(root);
  }
}

这三种写法都简单明了，一看就懂。下面的重点是三种遍历方式的非递归实现

要理解非递归实现，我们就要先清楚三种遍历的逻辑过程，以中序遍历为例：

• 想要访问节点p，就要先访问p的左子节点p.leftChild.
• 想要访问p.leftChild，同样也要先访问p的左子节点的子节点，p.leftChild.leftChild
• 依次类推，当p的左子节点以及左子节点的左子节点都访问完的时候，我们才可以访问P。这个时候P的指向应该是原来的root节点的最后一个左子节点
• 当访问完P的时候，我们要借助P来对P的右节点进行访问.
• 不断重复上一个过程，就可以中序遍历完整个二叉树

知道了这些，我们就可以大致写出代码了，代码中有注释，可以参考

public static void midTranverse(TreeNode root){
  TreeNode p = root;
  //stack用来存放我们第二和第三个步骤中遍历到的左子节点，我们要依靠这些左子节点来进入到他们对应的右树中去
  Stack<TreeNode> s = new Stack();
  while(p!= null || !s.isEmpty()){
    //按照思路，先让P节点的所有左子节点入栈
    while(p!=null){
      s.push(p);
      p = p.leftChild;
    }

    //这时候P应该为空，那么我们只能根据栈内是否有元素来判断是否要出栈了
    if(!s.isEmpty()){
      //注意，这里的if不能写成while，这样的话相当于全部出栈了，又回到了root节点，但是此时我们仅仅遍历了root节点左子树的所有左节点，还没有遍历左子树的所有右节点
      p=s.pop();
      //可以访问p了，因为这时候P指向root左子树的最后一个左子节点。
      visit(p);
      //虽然P是左子树的最后一个左子节点，但是P可能还会有右子节点，如果有的话，进入p的右子节点进行遍历，如果没有的话也没有关系，因为在下次大循环中P为空，还会继续取出我们原来栈内的元素进行遍历
      p=p.rightChild();
    }
  }
}

完整的代码就是这样，我们发现在外层循环的时候内层还有循环，这样效率不是很高，不过经过我们以上的分析，发现内层循环其实是可以省略的，代码如下

public static void midTranverse(TreeNode root){
  TreeNode p = root;
  Stack<TreeNode> s = new Stack();
  while(p!= null || !s.isEmpty()){
    if(p!=null){
      s.push(p);
      p=p.leftChild;
    }else{
      p = s.pop();
      visit(p);
      p=p.rightChild;
    }
  }
}

代码简洁了很多，基本思路没有变，都是当p不为空或者栈中还有元素的时候，不断循环，当p不为空的时候，我们要让p入栈，并进入p的左树，当p为空的时候，我们出栈，把栈顶元素赋给p，并进入p的右树。
这样就可以完成整个二叉树的中序遍历了。

前序遍历和中序遍历流程差不多，只是visit调用的实际不一样，前序遍历是在进入左树之前就会调用visit方法，中序遍历是在进入右树之前调用visit方法

非递归的后续遍历

后续遍历相比于前两种遍历困难的地方在于父节点必须在左右子树都遍历完的时候才能进行访问，我们需要有一个新的变量来记录是否已经访问完右子树了。

public static void postTranverse(TreeNode root){
  TreeNode p = root;
  TreeNode lastVisited = null;
  Stack<TreeNode> s = new Stack();
  
  //我们在判断是否可以访问一个节点时，都需要确保该节点的左子树和有子树都已经访问完了,为了能够确定该节点的左右子树都访问完了，先进入他左子树上每个节点是否都访问过
  while(p!=null){
    s.push(p);
    p=p.leftChild;
  }
  while(!s.isEmpty()){
    //取出栈顶元素
    p=s.pop();
    if(p.rightChild == null || p.rightChild == lastVisited){
      //当p的右子树为Null或者已经被访问过的时候，我们才能访问p
      visit(p);
      lastVisited = p;
    }else{
      //栈顶的元素现在右子树没有被访问过，则再次入栈，先不访问该元素
      s.push(p);
      p=p.rightChild;
      //然后去判断这个右子树是否被访问过
      while(p!=null){
        s.push(p);
        p=p.leftChild;
      }
    }
  }
}