二刷代碼隨想錄，在做二叉樹的時候總結一下規律，以加深對二叉樹的理解。

• 遞歸遍歷
  首先，回顧一下其他的數據結構，如數組，鏈表，棧和隊列，比較少的出現遞歸的操作，一遍都是直接遍歷循環。之所以在二叉樹的體系裏出現遞歸，和樹的數據結構的特點相關：由root節點和左右節點及節點的節點...構成。本質上是存在一個指針的不斷鏈接。因此和數組這種地址連續的結構相比，樹的節點沒有辦法通過依次尋找地址來遍歷。所以，遞歸派上了用場。倘若樹是一個單叉樹，問題倒沒有那麼複雜（不存在前序，後序，中序遍歷），只要不斷將子節點傳給遞歸函數，操作在遍歷之前或者之後。遞歸函數的意義可以理解為他通向最後不能在遞歸的地方為止。因此遞歸函數在代碼的位置非常重要，控制着代碼的邏輯。

• 遞歸遍歷的舉例
  以前序遍歷為例，前序遍歷是指中左右的遍歷方式，“前”是指中間節點首先遍歷。

  class Solution {
  public:
    void traversal(TreeNode* cur, vector<int>& result) {
        if (cur == NULL) return ;
        result.push_back(cur->val);
        traversal(cur->left, result);
        traversal(cur->right, result);
    }
  
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> ans;
        traversal(root, ans);
        return ans;
    }
  };

  1.首先是構造遞歸函數，首先他是個函數，得考慮傳入參數，返回值。傳入參數基本上肯定需要樹的節點傳入，這樣在函數裏面才能通過調用遞歸函數，並將當前的節點的左右節點傳入，實現遞歸的功能。
  2.順序。因為是前序遍歷，所以我們需要保證先對樹的中間節點進行操作，那麼由於傳入的root就是一箇中間節點，所以需要對其先進行操作。然後再traversal(left) , traversal(right)。

• 層序遍歷

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> result;
        queue<TreeNode*> que;
        if (root) que.push(root);
        while (!que.empty()) {
            int size = que.size();
            vector<int> vec;
            for (int i = 0; i < size; i++) {
                TreeNode* node = que.front();
                que.pop();
                vec.push_back(node->val);
                if (node->left) que.push(node->left);
                if (node->right) que.push(node->right);
            }
            result.push_back(vec);
        }
        return result;
    }
};

如何理解層序遍歷和普通遍歷之間的異同？在我看來，層序遍歷藴含的是前序遍歷的思想。首先在思考如何實現層序遍歷時，我們需要思考的問題的是如何避免樹在當前節點一直遞歸下去。因為如果那樣的話就無法實現一層一層的輸出了。所以我們需要構造一個容器去維護每一層的節點，這裏選擇隊列que。在遍歷當前節點的時候把他的左右節點依次放入隊列。然後再去實現遍歷一層的功能，十分的巧妙。

• 一個實例：翻轉二叉樹

class Solution {
public:
    void traversal(TreeNode* cur) {
        if (cur == NULL) return ;
        TreeNode* node = cur->left;
        cur->left = cur->right;
        cur->right = node; 
        traversal(cur->left);
        traversal(cur->right);
    }

    TreeNode* invertTree(TreeNode* root) {
        traversal(root);
        return root;
    }
};

可以用層序遍歷也可以用前序遍歷或者後續遍歷。這一次總結的時候在思考應該用什麼遍歷順序，想到了其實後序遍歷也是可以的，即可以把調用遞歸函數的兩行放在調換的前面。