二叉樹深度優先遍歷解題思路

1.二叉樹深度優先遍歷解題思路

1.1.三種深度優先遍歷的方式

• 理解深度優先遍歷的前提：
  
  任何一顆非空的二叉樹，都有根結點，左子樹和右子樹，例如上面這顆二叉樹，根結點是A，左子樹的結點有B、C、D，右子樹的結點有E、F，而任意一顆非空的二叉樹的左子樹和右子樹也是一顆二叉樹，
  
  上面這顆二叉樹的根為B，左子樹有C結點，右子樹有D結點， 以B為根結點的左子樹還是一顆二叉樹，
  
  上面這顆二叉樹的根結點是C，左子樹和右子樹是null，

• 先序遍歷（先根遍歷）
  先序遍歷指的是，對于任意一顆二叉樹，都先遍歷其根結點，然后遍歷其左子樹，最后遍歷其右子樹，
  
  例如上面這顆二叉樹，先序遍歷的結果就是A-B-C-D-E-F;

//先序遍歷
    public void preOrderTraversal(TreeNode root) {
        if (root == null) return;
        //對當前結點的實際作業 也可替換為其他陳述句
        System.out.print(root.val + " ");
        //實際作業結束
        this.preOrderTraversal(root.left);
        this.preOrderTraversal(root.right);
    }

• 中序遍歷（中根遍歷）
  中序遍歷指的是，對于任意一顆二叉樹，都先遍歷其左子樹，然后遍歷其根節點，最后遍歷其右子樹，
  
  例如上面這顆二叉樹，中序遍歷的結果就是C-B-D-A-E-F;

//中序遍歷
    public void inOrderTraversal(TreeNode root) {
        if (root == null) return;
        this.inOrderTraversal(root.left);
        //對當前結點的實際作業 也可替換為其他陳述句
        System.out.print(root.val + " ");
        //實際作業結束
        this.inOrderTraversal(root.right);
    }

• 后序遍歷（后根遍歷）
  后序遍歷指的是，對于任意一顆二叉樹，都先遍歷其左子樹，然后遍歷其右子樹，最后遍歷其根結點，
  

  例如上面這顆二叉樹，后序遍歷的結果就是C-D-B-F-E-A;

//后序遍歷
    public void postOrderTraversal(TreeNode root) {
        if (root == null) return;
        this.postOrderTraversal(root.left);
        this.postOrderTraversal(root.right);
        //對當前結點的實際作業 也可替換為其他陳述句
        System.out.print(root.val + " ");
        //實際作業結束
    }

1.2.深度優先遍歷的啟示

名詞說明：由于本人表達能力有限，下面所提到的一些名詞可能會讓讀者引起混淆，若在后面的文章閱讀程序中對某些名詞的含義產生了疑惑，可以翻到這里看一下對下面的出現的一些名詞的說明，

1. 結點實際操作：指本次遞回中對當前的結點（或含參）進行實際操作，
2. 結點實際操作順序：對某個資料結構的結點實際操作的順序，
3. 結點遍歷順序：結點實際操作順序，
4. 結點呼叫順序：指對某個資料結構中結點的實際訪問順序，或者說遞回時的函式堆疊幀的開辟順序，

1.2.1.遞回形成條件

我們都理解，深度優先遍歷的所使用的編碼技巧是遞回，而遞回有形成的條件有3個：

1. 函式呼叫自身
2. 有一個終止條件
3. 不斷朝終止條件步進

所謂的遞回，就是函式不斷呼叫自身的程序，在這個程序中，必須由一個終止遞回的條件，否則函式就會不斷地呼叫自身引發程式錯誤，那么問題就來了，既然是函式自己呼叫自己，所呼叫的函式名都是相同的，那么系統是怎么得知某次函式呼叫是最后一次，某次函式呼叫不是呢，答案是引數，不同的函式呼叫最大的區別就是函式引數， 一旦某次遞回呼叫的函式的引數達成了某個條件，系統就得知：“好了，我的函式引數已經達到了終止條件了，我不該再遞回下去了”，

我們都清楚了遞回的本質是對引數進行操作，一切都要圍繞引數進行，那么在單次的函式遞回中，想清楚自己究竟要做什么，應該考慮的點有哪些呢？

1. 下一次遞回的引數是什么？
2. 我該回傳什么？（為了回傳我想要的，我要怎么利用下一次遞回的回傳值？）
3. 我要對引數做什么？

也就是單次遞回，只要搞清楚遞什么（類似一個回旋鏢，遞什么引數，它回傳什么），歸（自己回傳什么）什么就行了，

1.2.2遞回程序的實際作業順序

我們已經知道單次遞回要做什么了，但整個遞回的程序的考慮不應該只有這些，還有一個很重要的問題，在一次遞回呼叫中，我既要把引數傳給下一次遞回并獲得下一次遞回的回傳值（也可能沒回傳值），又要對引數操作，那操作當前引數和進行下一次遞回，誰先誰后呢？

1.2.2.1.單路遞回的實際作業順序

所謂的單路遞回，即在某次遞回呼叫中，最多遞回呼叫自己一次，典型的有對單鏈表進行遞回，下次進行遞回的引數就是自己的后繼結點，

就單路遞回，某一次函式呼叫，根據下一次函式呼叫和本次函式呼叫的作業的先后順序，可以分為：

1. 我先把引數B（當前結點的后繼）遞給下一次遞回， 等下一次遞回回傳的時候，我再操作引數A（當前結點），然后我再回傳，
2. 我先操作引數A（當前結點），然后把引數B（當前結點的后繼）遞給下一次遞回，等這個遞回回傳后，我再接受它的回傳值，最后再回傳我想要回傳的值，

發現沒有，就單路遞回而言，操作引數和把遞給下一次遞回的先后順序不同，你對單鏈表的實際操作順序就不同了，第一種遞回你從后往前操作單鏈表，第二個遞回則是從前往后操作單鏈表， 換句話來說，第一種是逆向遍歷單鏈表，第二種是正向遍歷單鏈表，

當然還有不同的先后順序安排，這里不再列舉，只是想通過這個例子讓你知道在單路遞回中，函式呼叫中的下一次遞回的和操作當前引數的執行先后順序不同，實際的操作順序截然不同，

這里也就得出了一個重要結論，遍歷指的就是實際的業務操作順序，而不是呼叫順序，

1.2.2.2. 雙路遞回的實際作業順序

雙路遞回顧名思義，每次函式呼叫都會遞回呼叫兩次，典型的有對二叉樹進行深度優先遍歷，對某個結點遞回后，該節點的左右孩子也會參與遞回，想一下對二叉樹雙路遞回的不同的業務操作時機對實際二叉樹結點的操作順序的影響，你可能就已經開始頭疼了，

列舉三個在遞回二叉樹時，操作當前結點和進行下一次遞回的不同先后順序組合：

1在單次遞回呼叫中，我先操作引數（當前根結點），然后遞回呼叫左孩子結點，再遞回呼叫右孩子結點，最后回傳，
2在單次遞回呼叫中，我先遞回呼叫左孩子結點，然后操作引數（當前根結點），再遞回呼叫右孩子結點，
1在單次遞回呼叫中，我先遞回呼叫左孩子結點，然后遞回呼叫右孩子結點，再操作當前引數（當前根結點），

問：這三種情況，二叉樹結點的實際操作順序是什么樣的？

實際上，這三種遞回方式說的的就是先序遍歷，中序遍歷和后序遍歷，可以多多體會一下，

1.2.3.三種深度優先遍歷給我們的啟示是什么？

實際上，三種優先遍歷告訴了我們遞回程序中對二叉樹結點的實際操作順序，所謂的不同深度優先遍歷方式等價于不同的二叉樹結點實際操作順序， 你會發現，三種深度優先遍歷方式對二叉樹結點的函式呼叫順序都是相同的，但實際操作結點的順序卻是不同的，

例如后序遍歷，從函式呼叫來看，你的函式呼叫的結點也是A-B-C，但實際操作的第一個結點卻是C，演示如下：

1. 你在呼叫了A這個結點后，還沒來得及操作，就馬上遞回呼叫B結點，

2. 同理B結點呼叫之后，你也還沒操作，你就遞回呼叫了C結點，

3. 還沒來得及操作C，你又遞回呼叫了C的左子樹（空節點），檢測到 引數不合法，遞回回傳到C結點中，

4. C左子樹遞回呼叫回傳之后，才對C結點進行了實際的操作，

• 不管是哪一種深度優先遍歷方式（先序，中序和后序），結點呼叫的順序都是相同的，對結點的實際操作順序卻是不同的，

1.3.深度優先遍歷二叉樹解題模板

根據1.2的推論，我們可以對二叉樹深度優先遍歷的題目的解法得出一個結論：只要知道某道題的合適的深度優先遍歷方式（實際作業順序），遞回的引數，回傳的引數，就可以解答了，

1. 確定某道二叉樹題目適合深度優先遍歷，且知道最佳的深度遍歷方式，
2. 根據深度遍歷方式設計單次遞回模板
   先序遍歷：操作當前結點-左路遞回-右路遞回-回傳
   中序遍歷：左路遞回-操作當前結點-右路遞回-回傳
   后序遍歷：左路遞回-右路遞回-操作當前結點-回傳
3. 確定左路遞回和右路遞回的引數和回傳值
4. 編碼

當然，并非所有的二叉樹深度遍歷題都適用這個模板，因為除了這三種還有其他的深度優先遍歷方式，例如你可以——操作當前結點-右路遞回-左路遞回-回傳，但在理解了最常見的三種深度遍歷方式，其他的深度遍歷方式可以類推了，

1.4.二叉樹深度優先遍歷題目的一些補充

對于一些特殊的深度優先遍歷的題目，特別是一次遞回的實際作業中需要操作一個以上二叉樹結點的，由于一般來說一次函式呼叫我們只有一個結點的引數，不太好定位到其他的結點，所以我們可以考慮使用成員變數作為我們的輔助變數，

例題：

描述
輸入一棵二叉搜索樹，將該二叉搜索樹轉換成一個排序的雙向鏈表，如下圖所示

資料范圍：輸入二叉樹的節點數 0≤n≤10000 \le n \le 10000≤n≤1000，二叉樹中每個節點的值 0≤val≤10000\le val \le 10000≤val≤1000
要求：空間復雜度O(1)O(1)O(1)（即在原樹上操作），時間復雜度 O(n)O(n)O(n)

注意:
1.要求不能創建任何新的結點，只能調整樹中結點指標的指向，當轉化完成以后，樹中節點的左指標需要指向前驅，樹中節點的右指標需要指向后繼
2.回傳鏈表中的第一個節點的指標
3.函式回傳的TreeNode，有左右指標，其實可以看成一個雙向鏈表的資料結構
4.你不用輸出雙向鏈表，程式會根據你的回傳值自動列印輸出
輸入描述：
二叉樹的根節點
回傳值描述：
雙向鏈表的其中一個頭節點，
示例1
輸入：

{10,6,14,4,8,12,16}

回傳值：

From left to right are:4,6,8,10,12,14,16;From right to left are:16,14,12,10,8,6,4;

說明：

輸入題面圖中二叉樹，輸出的時候將雙向鏈表的頭節點回傳即可，

示例2
輸入：

{5,4,#,3,#,2,#,1}

回傳值：

From left to right are:1,2,3,4,5;From right to left are:5,4,3,2,1;

說明：

                5
              /
            4
          /
        3
      /
    2
  /
1

樹的形狀如上圖

題解

/**
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/
//中序遍歷二叉樹 并改變當前二叉樹的結點的左子樹指向和前一個操作的二叉樹的右子樹指向（用成員變數存盤）
public class Solution {
	//用成員變數記錄上一次遍歷的結點
    public TreeNode prev;
    public void inOrder(TreeNode root) {
        //遞回結束條件判定
        if (root == null) return;
        //先遞回左子樹
        inOrder(root.left);
        //具體的作業
        root.left = prev;
        if (prev != null) prev.right = root;
        prev = root;
        //作業結束
        //遞回右子樹
        inOrder(root.right);
    }
    public TreeNode Convert(TreeNode root) {
        if (root == null) return null;
        inOrder(root);
        while (root.left != null) root = root.left;
        return root;
    }
}