4.二叉樹的先序、中序以及後序周遊的遞歸寫法與非遞歸寫法（LeetCode第94、144、145題）

一、遞歸法

這次我們要好好談一談遞歸，為什麼很多同學看遞歸算法都是“一看就會，一寫就廢”。

主要是對遞歸不成體系，沒有方法論，每次寫遞歸算法 ，都是靠玄學來寫代碼，代碼能不能編過都靠運氣。

本篇将介紹前後中序的遞歸寫法，一些同學可能會感覺很簡單，其實不然，我們要通過簡單題目把方法論确定下來，有了方法論，後面才能應付複雜的遞歸。

這裡幫助大家确定下來遞歸算法的三個要素。每次寫遞歸，都按照這三要素來寫，可以保證大家寫出正确的遞歸算法！

1.确定遞歸函數的參數和傳回值：

确定哪些參數是遞歸的過程中需要處理的，那麼就在遞歸函數裡加上這個參數， 并且還要明确每次遞歸的傳回值是什麼進而确定遞歸函數的傳回類型。

2.确定終止條件：

寫完了遞歸算法, 運作的時候，經常會遇到棧溢出的錯誤，就是沒寫終止條件或者終止條件寫的不對，作業系統也是用一個棧的結構來儲存每一層遞歸的資訊，如果遞歸沒有終止，作業系統的記憶體棧必然就會溢出。

3.确定單層遞歸的邏輯：

确定每一層遞歸需要處理的資訊。在這裡也就會重複調用自己來實作遞歸的過程。

以下以前序周遊為例：

**确定遞歸函數的參數和傳回值：**因為要列印出前序周遊節點的數值，是以參數裡需要傳入vector在放節點的數值，除了這一點就不需要在處理什麼資料了也不需要有傳回值，是以遞歸函數傳回類型就是void，代碼如下：

void traversal(TreeNode cur, vector& vec)*

**确定終止條件：**在遞歸的過程中，如何算是遞歸結束了呢，當然是目前周遊的節點是空了，那麼本層遞歸就要要結束了，是以如果目前周遊的這個節點是空，就直接return，代碼如下：

if (cur == NULL) return;

**确定單層遞歸的邏輯：**前序周遊是中左右的循序，是以在單層遞歸的邏輯，是要先取中節點的數值，代碼如下：

vec.push_back(cur->val); // 中

traversal(cur->left, vec); // 左

traversal(cur->right, vec); // 右

單層遞歸的邏輯就是按照中左右的順序來處理的，這樣二叉樹的前序周遊，基本就寫完了，在看一下完整代碼：

二、先序周遊的遞歸寫法

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
         
         ArrayList<Integer> list = new ArrayList<>();
         preorder(root,list);
         return list;
    }

    private void preorder(TreeNode root,List<Integer> list)
    {
        if(root == null)
        {
            return;
        }
        list.add(root.val);
        preorder(root.left,list);
        preorder(root.right,list);
    }
}
           

三、先序周遊的非遞歸寫法

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
         
         List<Integer> list = new ArrayList<>();
         Stack<TreeNode> stack = new Stack<>();
         while(root != null || !stack.isEmpty())
         {
             while(root != null)
             {
                 list.add(root.val);
                 stack.push(root);
                 root = root.left;
             }
             TreeNode cur = stack.pop();
             root = cur.right;
         }
         return list;
    }
}
           

四、中序周遊的遞歸寫法

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
         
         ArrayList<Integer> list = new ArrayList<>();
         inorder(root,list);
         return list;
    }

    public void inorder(TreeNode root,List<Integer> list)
    {
        if(root == null)
        {
            return;
        }
        inorder(root.left,list);
        list.add(root.val);
        inorder(root.right,list);
    }
}
           

五、中序周遊的非遞歸寫法

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
         
         ArrayList<Integer> list = new ArrayList<>();
         Stack<TreeNode> stack = new Stack<>();
         while(root != null || !stack.isEmpty())
         {
             while(root != null)
             {
                 stack.push(root);
                 root = root.left;
             }
             root = stack.pop();
             list.add(root.val);
             root = root.right;
         }
         return list;
    }
}
           

六、後序周遊的遞歸寫法

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
         
         ArrayList<Integer> list = new ArrayList<>();
         postorder(root,list);
         return list;
    }

    private void postorder(TreeNode root,List<Integer> list)
    {
        if(root == null)
        {
            return;
        }
        postorder(root.left,list);
        postorder(root.right,list);
        list.add(root.val);
    }
}
           

七、後序周遊的非遞歸寫法

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
         
         ArrayList<Integer> list = new ArrayList<>();
         Stack<TreeNode> stack = new Stack<>();
         while(root != null || !stack.isEmpty())
         {
             while(root != null)
             {
                 list.add(root.val);
                 stack.push(root);
                 root = root.right;
             }
             TreeNode cur = stack.pop();
             root = cur.left;
         }
         Collections.reverse(list);
         return list;
    }
}