現(xiàn)在決定把自己很久以前的一些文章重新markdown一下，發(fā)到簡書來，先從這篇二叉樹的遍歷說起的。
大家都知道二叉樹的遍歷分為前序遍歷，中序遍歷，后序遍歷。記得大學學習這一部分的時候，覺得用遞歸就可以輕易實現(xiàn)，簡直太簡單了，所以也就沒有認真學，不過后來面試的時候考官要寫一下二叉樹的中序遍歷，而且不能用遞歸，當時就很尷尬了，所以現(xiàn)在把二叉樹的每種遍歷思想和方法都記錄一下，做個備忘

遞歸的解法來解決前序中序和后續(xù)的遍歷

這簡直是太簡單不過了

遞歸前序遍歷

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

是不是非常言簡意賅，遍歷的時候先訪問本身，然后遍歷左節(jié)點，接著遍歷右節(jié)點，而且簡單易懂，接下來直接寫中序遍歷和后續(xù)遍歷，思路是一樣的

遞歸中序遍歷

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

遞歸后續(xù)遍歷

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

這三種寫法都簡單明了，一看就懂。下面的重點是三種遍歷方式的非遞歸實現(xiàn)

要理解非遞歸實現(xiàn)，我們就要先清楚三種遍歷的邏輯過程，以中序遍歷為例：

• 想要訪問節(jié)點p，就要先訪問p的左子節(jié)點p.leftChild.
• 想要訪問p.leftChild，同樣也要先訪問p的左子節(jié)點的子節(jié)點，p.leftChild.leftChild
• 依次類推，當p的左子節(jié)點以及左子節(jié)點的左子節(jié)點都訪問完的時候，我們才可以訪問P。這個時候P的指向應該是原來的root節(jié)點的最后一個左子節(jié)點
• 當訪問完P(guān)的時候，我們要借助P來對P的右節(jié)點進行訪問.
• 不斷重復上一個過程，就可以中序遍歷完整個二叉樹

知道了這些，我們就可以大致寫出代碼了，代碼中有注釋，可以參考

public static void midTranverse(TreeNode root){
  TreeNode p = root;
  //stack用來存放我們第二和第三個步驟中遍歷到的左子節(jié)點，我們要依靠這些左子節(jié)點來進入到他們對應的右樹中去
  Stack<TreeNode> s = new Stack();
  while(p!= null || !s.isEmpty()){
    //按照思路，先讓P節(jié)點的所有左子節(jié)點入棧
    while(p!=null){
      s.push(p);
      p = p.leftChild;
    }

    //這時候P應該為空，那么我們只能根據(jù)棧內(nèi)是否有元素來判斷是否要出棧了
    if(!s.isEmpty()){
      //注意，這里的if不能寫成while，這樣的話相當于全部出棧了，又回到了root節(jié)點，但是此時我們僅僅遍歷了root節(jié)點左子樹的所有左節(jié)點，還沒有遍歷左子樹的所有右節(jié)點
      p=s.pop();
      //可以訪問p了，因為這時候P指向root左子樹的最后一個左子節(jié)點。
      visit(p);
      //雖然P是左子樹的最后一個左子節(jié)點，但是P可能還會有右子節(jié)點，如果有的話，進入p的右子節(jié)點進行遍歷，如果沒有的話也沒有關(guān)系，因為在下次大循環(huán)中P為空，還會繼續(xù)取出我們原來棧內(nèi)的元素進行遍歷
      p=p.rightChild();
    }
  }
}

完整的代碼就是這樣，我們發(fā)現(xiàn)在外層循環(huán)的時候內(nèi)層還有循環(huán)，這樣效率不是很高，不過經(jīng)過我們以上的分析，發(fā)現(xiàn)內(nèi)層循環(huán)其實是可以省略的，代碼如下

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不為空或者棧中還有元素的時候，不斷循環(huán)，當p不為空的時候，我們要讓p入棧，并進入p的左樹，當p為空的時候，我們出棧，把棧頂元素賦給p，并進入p的右樹。
這樣就可以完成整個二叉樹的中序遍歷了。

前序遍歷和中序遍歷流程差不多，只是visit調(diào)用的實際不一樣，前序遍歷是在進入左樹之前就會調(diào)用visit方法，中序遍歷是在進入右樹之前調(diào)用visit方法

非遞歸的后續(xù)遍歷

后續(xù)遍歷相比于前兩種遍歷困難的地方在于父節(jié)點必須在左右子樹都遍歷完的時候才能進行訪問，我們需要有一個新的變量來記錄是否已經(jīng)訪問完右子樹了。

public static void postTranverse(TreeNode root){
  TreeNode p = root;
  TreeNode lastVisited = null;
  Stack<TreeNode> s = new Stack();
  
  //我們在判斷是否可以訪問一個節(jié)點時，都需要確保該節(jié)點的左子樹和有子樹都已經(jīng)訪問完了,為了能夠確定該節(jié)點的左右子樹都訪問完了，先進入他左子樹上每個節(jié)點是否都訪問過
  while(p!=null){
    s.push(p);
    p=p.leftChild;
  }
  while(!s.isEmpty()){
    //取出棧頂元素
    p=s.pop();
    if(p.rightChild == null || p.rightChild == lastVisited){
      //當p的右子樹為Null或者已經(jīng)被訪問過的時候，我們才能訪問p
      visit(p);
      lastVisited = p;
    }else{
      //棧頂?shù)脑噩F(xiàn)在右子樹沒有被訪問過，則再次入棧，先不訪問該元素
      s.push(p);
      p=p.rightChild;
      //然后去判斷這個右子樹是否被訪問過
      while(p!=null){
        s.push(p);
        p=p.leftChild;
      }
    }
  }
}