一、樹的基礎知識

（一）樹的基本結構

在二叉樹中的每個節點最多只有兩個子節點，可以分別把它們稱為左子節點和右子節點。二叉樹的根節點沒有父節點，一顆非空二叉樹只有一個父節點。二叉樹的葉節點沒有子節點。

名詞說明：葉節點：如果一個節點沒有子節點，那麼它是一個葉節點。例如在圖 1 的二叉樹中，節點 4、節點 5、節點 6、節點 7 都沒有子節點，故節點 4、5、6、7 都是葉節點。

（二）二叉樹的遞歸性質

二叉樹是一種典型的具有遞歸性質的數據結構。二叉樹的根節點可能有子節點，子節點又是對應子樹的根節點，該節點可能也有自己的子節點。

例如圖 1 中的節點 1 是該二叉樹的根節點，節點 1 有左子節點 2、右子節點 3。而節點 2 是左子樹的根節點，節點 2 也有子節點。

既然有遞歸性質，那麼自然可以用遞歸來遍歷二叉樹。

（三）創建二叉樹

定義二叉樹數據結構

class Node{
 public $left  = NULL;
 public $right = NULL;
 public $data;
 public function __construct($data){
  $this->data = $data;
 }
}

二、中序遍歷

（一）什麼是中序遍歷？

先遍歷二叉樹的左子樹，再遍歷二叉樹的根節點，最後遍歷二叉樹的右子樹。

例如，如果中序遍歷圖 1 中的二叉樹，則先後遍歷節點 4、節點 2、節點 5、節點 1、節點 6、節點 3、節點 7。

（二）遞歸實現

（1）參考代碼：

class Tree{
 public $nodes = [];
        // Node 類是前文的創造二叉樹的 Node 類。
 public function inorderTraversal(Node $root){
  $this->dfs($root,$this->nodes);
  return $this->nodes;
 }
 public function dfs($root,$nodes){
  if($root != NULL){
   $this->dfs($root->left,$nodes);
   $this->nodes[] = $root->data;
   $this->dfs($root->right,$nodes);
  }
 }
}

（2）代碼分析：在我之前寫的《遞歸十誡》幾篇博客中，遞歸的對象是列表。在遞歸二叉樹時，也可以參考《遞歸十誡》。

① 第一誡：在遞歸列表時，將 empty 作為諸問題之首；根據二叉樹的遞歸性質可以得出，在遞歸二叉樹時，將根節點是否為空作為諸問題之首。其實也很好理解：當輸入的是一個空二叉樹時，就不能進行遞歸。

public function dfs($root,$nodes){
    if($root != NULL){
    ...
    }
}

② 第四誡：至少改變一個參數，該參數必須向著不斷接近結束條件的方向而改變，改變的參數必須在結束時得以測試。在這裡，主要改變的是根節點。將當前根節點的左右子節點作為下一次調用的根節點。

public function dfs($root,$nodes){
    ...
    $this->dfs($root->left,$nodes);
    ...
    $this->dfs($root->right,$nodes);
    ...
}

③ 先後順序：根據中序遍歷的順序，應該先對左子樹遞歸，再遍歷根節點，最後對右子樹遞歸。

（三）疊代實現

在用疊代實現之前，需要先搞明白這篇博客的主題——深度優先搜索。（1）什麼是深度優先搜索？

深度優先遍歷（Depth First Search），簡稱DFS，其原則是，沿著一條路徑一直找到最深的那個節點，當沒有子節點的時候，返回上一級節點，尋找其另外的子節點，繼續向下遍歷，沒有就向上返回一級，直到所有的節點都被遍歷到，每個節點只能訪問一次^1。

（2）參考代碼：

class Tree{
 public $nodes = [];
 public $stack = [];
 public function inorderTraversal(Node $root){
  $cur = $root;
  while($cur != NULL || !empty($this->stack)){
   while($cur != NULL){
    array_push($this->stack,$cur);
    $cur = $cur->left;
   }
   $cur = array_pop($this->stack);
   array_push($this->nodes,$cur->data);
   $cur = $cur->right;
  }
  return $this->nodes;
 }
}

（3）代碼分析： ① 順著當前節點的左子節點的指針一路向左，直到遇到第一個缺少左子節點的節點 N，並將沿途遇到的節點存入棧中。此時棧頂就是在一路向左的路上遇到的第一個缺少左子節點的節點 N。

public function inorderTraversal(Node $root)
{
 // 變量 cur 表示當前遍歷的節點。
 $cur = $root;
 while ($cur != null || !empty($this->stack)) {
  while ($cur != null) {
   array_push($this->stack, $cur);
   $cur = $cur->left;
  }
  ...
 }
 ...
}

② 節點 N 出棧，保存節點 N 的值。 ③ 將當前節點的值更新為節點 N 的右子節點。再次循環，②、③ 步驟代碼如下：

public function inorderTraversal(Node $root)
{
 $cur = $root;
 while ($cur != null || !empty($this->stack)) {
  ...
  $cur = array_pop($this->stack);
  array_push($this->nodes, $cur->data);
  $cur = $cur->right;
 }
 return $this->nodes;
}

總結：一直向左走到黑，直到遇到節點 N（第一個缺少左子節點的節點），左走不通了，再看看節點 N 的右邊能不能走通：

如果能走通，就繼續一路向左走。
如果走不通，返回節點 N 的根節點 R，再走向節點 R 的右邊，然後繼續往左走。

如此循環往復，直到遍歷了所有節點。

三、前序遍歷

（一）什麼是前序遍歷？

先遍歷二叉樹的根節點，再遍歷二叉樹的左子樹，最後遍歷二叉樹的右子樹。

例如，如果前序遍歷圖 1 中的二叉樹，則先後遍歷節點 1、節點 2、節點 4、節點 5、節點 3、節點 6、節點 7。

（二）遞歸實現

前序遍歷的遞歸代碼實現和中序遍歷的遞歸代碼實現類似，只需要調整遞歸函數中代碼的順序即可。

class Tree{
 public $nodes = [];
 public function inorderTraversal(Node $root){
  $this->dfs($root,$this->nodes);
  return $this->nodes;
 }
 public function dfs($root,$nodes){
  if($root != NULL){
   $this->nodes[] = $root->data;
   $this->dfs($root->left,$nodes);
   $this->dfs($root->right,$nodes);
  }
 }
}

（三）疊代實現

前序遍歷的疊代代碼類似於中序遍歷的疊代代碼。

它們之間唯一的區別在於順著左子節點的指針向下移動時，前序遍歷將遍歷遇到的每個節點添加到棧中。

這是由前序遍歷的順序決定的，前序遍歷是先遍歷根節點，再遍歷它的左子節點。

class Tree{
 public $nodes = [];
 public $stack = [];
 public function preOrderTraversal(Node $root){
  $cur = $root;
  while($cur != NULL || !empty($this->stack)){
   while($cur != NULL){
    array_push($this->nodes,$cur->data);
    array_push($this->stack,$cur);
    $cur = $cur->left;
   }
   $cur = array_pop($this->stack);
   $cur = $cur->right;
  }
  return $this->nodes;
 }
}

四、後序遍歷

（一）什麼是後序遍歷？

先遍歷二叉樹的左子樹，再遍歷二叉樹的右子樹，最後遍歷二叉樹的根節點。

例如，如果前序遍歷圖 1 中的二叉樹，則先後遍歷節點 4、節點 5、節點 2、節點 6、節點 7、節點 3、節點 1。

（二）遞歸實現

後序遍歷的遞歸代碼實現和中序遍歷的遞歸代碼實現類似，只需要調整遞歸函數中代碼的順序即可。

class Tree{
 public $nodes = [];
 public function postOrderTraversal(Node $root){
  $this->dfs($root,$this->nodes);
  return $this->nodes;
 }
 public function dfs($root,$nodes){
  if($root != NULL){
   $this->dfs($root->left,$nodes);
   $this->dfs($root->right,$nodes);
   $this->nodes[] = $root->data;
  }
 }
}

（三）疊代實現

和中序遍歷、前序遍歷相比，後序遍歷的疊代代碼要稍微複雜一點。

當達到某個節點時：

如果之前還沒遍歷過它的右子樹就得前往它的右子節點。
如果之前已經遍歷過它的右子樹那麼就可以遍歷這個節點。

也就是說，此時要根據它的右子樹此前沒有遍歷過來確定是否應該遍歷當前的節點：

如果此前右子樹中最後一個遍歷的節點應該是右子樹的根節點，也就是當前節點的右子節點。可以記錄遍歷的前一個節點。
如果一個節點存在右子節點並且右子節點正好是前一個被遍歷的節點，那麼它的右子樹已經被遍歷過，現在是時候遍歷當前節點了。

class Tree{
 public $nodes = [];
 public $stack = [];
 public function postOrderTraversal(Node $root){
  $cur  = $root;
  $prev = NULL;
  while($cur != NULL || !empty($this->stack)){
   while($cur != NULL){
    array_push($this->stack,$cur);
    $cur = $cur->left;
   }
   $cur = $this->stackPeek($this->stack);
   if($cur->right != NULL && $cur->right != $prev){
    $cur = $cur->right;
   }else{
    array_pop($this->stack);
    $this->nodes[] = $cur->data;
    $prev = $cur;
    $cur  = NULL; 
   }
  }
  return $this->nodes;
 }
 public function stackPeek($stack){
  return $stack[count($stack)-1];
 }
}

總結：只有當棧頂元素的右子節點不為空且不等於前一節點時，才能走右邊。

小夥伴們有興趣想了解內容和更多相關學習資料的請點讚收藏+評論轉發+關注我，後面會有很多乾貨。我有一些面試題、架構、設計類資料可以說是程式設計師面試必備！

所有資料都整理到網盤了，需要的話歡迎下載！私信我回復【111】即可免費獲取

作者：Moonshadow2333

連結：https://mdnice.com/writing/1d3e1969f3ed43cbbb6fe1c9e1c354b9

《劍指offer》之二叉樹的深度優先搜索

一、樹的基礎知識

（一）樹的基本結構

（二）二叉樹的遞歸性質

（三）創建二叉樹

二、中序遍歷

（一）什麼是中序遍歷？

（二）遞歸實現

（三）疊代實現

三、前序遍歷

（一）什麼是前序遍歷？

（二）遞歸實現

（三）疊代實現

四、後序遍歷

（一）什麼是後序遍歷？

（二）遞歸實現

（三）疊代實現