Day16 二叉树的递归遍历，迭代遍历，层序遍历

递归遍历

每次写递归，都要考虑三要素：

1、确定递归函数的参数和返回值：哪些参数是递归的过程中要处理的，那么就在递归函数里加入这个参数，并且还要明确每次递归的返回值是什么进而确定递归函数的返回类型。

2、确定终止条件。

3、确定单层递归的逻辑：确定每一层递归需要处理的信息，就可以重复调用自己来实现递归。

? ? ? ? 下面以前序遍历为例：

1、确定递归函数的参数和返回值：因为要打印前序遍历节点的数值，所以参数里需要传入vector来存放数值，同时不需要返回值，代码如下：

void traversal(TreeNode* cur, vector<int>& vec)

?2、确定终止条件：如果当前遍历的结点是空，那么本层递归就要结束了，代码如下；

if (cur == NULL) return;

?3、确定单层递归的逻辑：前序遍历是中左右的顺序，代码如下：

vec.push_back(cur->val);    // 中
traversal(cur->left, vec);  // 左
traversal(cur->right, vec); // 右

? ? ? ? ?这样就写完了前序递归的代码，完整的代码如下：

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

? ? ? ? 中序遍历和后序遍历只有单层递归的逻辑不同，其余都一样。

void traversal(TreeNode* cur, vector<int>& vec) {
    if (cur == NULL) return;
    traversal(cur->left, vec);  // 左
    vec.push_back(cur->val);    // 中
    traversal(cur->right, vec); // 右
}

void traversal(TreeNode* cur, vector<int>& vec) {
    if (cur == NULL) return;
    traversal(cur->left, vec);  // 左
    traversal(cur->right, vec); // 右
    vec.push_back(cur->val);    // 中
}

?迭代遍历

前序遍历（迭代法）

? ? ? ? ?整体的思路如下：先建立一个栈用来存放已经访问过的元素，定义一个vector存储结果。如果根节点为空，则直接return。先将根节点root压入栈中，进入一个while循环，定义一个node=栈顶元素，弹出，再将其value放入result中，同时如果左右孩子存在，就将左右孩子入栈，注意要先入右，因为栈弹出的时候是先进后出。这样就能够按照中左右的顺序实现前序遍历，代码如下：

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        stack<TreeNode*> st;
        vector<int> result;
        if (root == NULL) return result;
        st.push(root);
        while (!st.empty()) {
            TreeNode* node = st.top();                       // 中
            st.pop();
            result.push_back(node->val);
            if (node->right) st.push(node->right);           // 右（空节点不入栈）
            if (node->left) st.push(node->left);             // 左（空节点不入栈）
        }
        return result;
    }
};

?后序遍历（迭代法）

? ? ? ? 先序遍历是中左右，如果调整先序遍历中的左右顺序，那么就变成了中右左，反转以下就变成了左右中，也就是后序遍历的形式，所以我们只要在上面的代码上进行修改即可。

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        stack<TreeNode*> st;
        vector<int> result;
        if (root == NULL) return result;
        st.push(root);
        while (!st.empty()) {
            TreeNode* node = st.top();
            st.pop();
            result.push_back(node->val);
            if (node->left) st.push(node->left); // 相对于前序遍历，这更改一下入栈顺序 （空节点不入栈）
            if (node->right) st.push(node->right); // 空节点不入栈
        }
        reverse(result.begin(), result.end()); // 将结果反转之后就是左右中的顺序了
        return result;
    }
};

?中序遍历（迭代法）

? ? ? ? 既然后序遍历都可以对前序遍历的代码进行修改，那么中序遍历是否也可以呢？答案是不行。注意迭代过程中右两个操作：1、访问：遍历结点。2、处理：将元素放入result数组中。因为前序遍历的顺序是中左右，先访问的元素是中间节点，要处理的元素也是中间节点，要访问和处理的元素是一致的，都是中间节点所以可以访问。而中序遍历是左中右，先访问的事二叉树顶部的节点，然后一层一层向下访问，直到到达左下方的最底部，才开始处理结点，这导致了访问顺序和处理顺序的不一致。所以我们采用指针的遍历来帮助访问节点，用栈来处理结点。

?????????代码的整体思路是这样的：首先还是创建一个result和stack，这时定义一个指针cur指向root，这时候开始while循环，条件是cur不为空或者栈不为空，cur不为空说明还有结点要处理，因为在中序遍历中，我们沿着左子树一直走到底部时，当前节点可能还有右子树需要继续处理，栈不为空说明还有节点等待处理，因为处理完一个结点的左子树以后，需要回溯到其父节点，然后处理父节点的右子树。中间用或是因为处理完最后一个结点的右子树后，仍然需要回溯到根节点。

? ? ? ? 接下来是while里面的语句。如果结点不为空，就持续进栈往左访问，同时都存入栈中，直到访问到了最左边的最后一个元素位置，举个例子，像1这种情况，如果左右孩子都没有并且作为上一个的左孩子，再经过遍历后cur会处于栈中4的位置，之后4会访问2，如果是2这种情况，左右孩子都没有并且作为上一个结点的右孩子，再访问完以后就会直接回到5。总之，可这左先访问到头，之后访问左的上面，再访问右，之后直接退回到上上的爷爷结点。代码如下：

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> result;
        stack<TreeNode*> st;
        TreeNode* cur = root;
        while (cur != NULL || !st.empty()) {
            if (cur != NULL) { // 指针来访问节点，访问到最底层
                st.push(cur); // 将访问的节点放进栈
                cur = cur->left;                // 左
            } else {
                cur = st.top(); // 从栈里弹出的数据，就是要处理的数据（放进result数组里的数据）
                st.pop();
                result.push_back(cur->val);     // 中
                cur = cur->right;               // 右
            }
        }
        return result;
    }
};

? ? ? ? ?那么能不能像递归遍历一样，直接改动一点点代码就能让前中后序遍历变得简单呢？其实是可以的，请看下文。

?二叉树的统一迭代法：

? ? ? ? 具体的方法就是要处理访问节点和处理结点不一致的情况，那么我们就将访问的结点放入栈中，要处理的结点也放入栈中但是要做标记。

? ? ? ? 以中序遍历为例：依旧创建result和stack，同时判断一下根节点是否为空，之后进入循环，定义一个node指向栈顶，如果node不为空，那就先将其弹出来，因为后面要加三个，会重复，在加入中节点时，要同时加一个null来表示中节点访问过但没有处理的标记。当遇到空节点的时候，也就是要处理中节点了，先将空节点弹出，将这个元素存到result里即可，代码如下：

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> result;
        stack<TreeNode*> st;
        if (root != NULL) st.push(root);
        while (!st.empty()) {
            TreeNode* node = st.top();
            if (node != NULL) {
                st.pop(); // 将该节点弹出，避免重复操作，下面再将右中左节点添加到栈中
                if (node->right) st.push(node->right);  // 添加右节点（空节点不入栈）

                st.push(node);                          // 添加中节点
                st.push(NULL); // 中节点访问过，但是还没有处理，加入空节点做为标记。

                if (node->left) st.push(node->left);    // 添加左节点（空节点不入栈）
            } else { // 只有遇到空节点的时候，才将下一个节点放进结果集
                st.pop();           // 将空节点弹出
                node = st.top();    // 重新取出栈中元素
                st.pop();
                result.push_back(node->val); // 加入到结果集
            }
        }
        return result;
    }
};

?????????对于前序和后续遍历，仅仅就是换了两行代码的顺序而已。这样，只有将空节点弹出时，才将下一个节点放进结果集。

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> result;
        stack<TreeNode*> st;
        if (root != NULL) st.push(root);
        while (!st.empty()) {
            TreeNode* node = st.top();
            if (node != NULL) {
                st.pop();
                if (node->right) st.push(node->right);  // 右
                if (node->left) st.push(node->left);    // 左
                st.push(node);                          // 中
                st.push(NULL);
            } else {
                st.pop();
                node = st.top();
                st.pop();
                result.push_back(node->val);
            }
        }
        return result;
    }
};

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> result;
        stack<TreeNode*> st;
        if (root != NULL) st.push(root);
        while (!st.empty()) {
            TreeNode* node = st.top();
            if (node != NULL) {
                st.pop();
                if (node->right) st.push(node->right);  // 右
                if (node->left) st.push(node->left);    // 左
                st.push(node);                          // 中
                st.push(NULL);
            } else {
                st.pop();
                node = st.top();
                st.pop();
                result.push_back(node->val);
            }
        }
        return result;
    }
};

层序遍历

? ? ? ? 层序遍历一个二叉树，需要借用一个辅助数据结构来实现，队列先进先出，符合一层一层遍历的逻辑，栈先进后出符合递归的逻辑。

????????

? ? ? ? ?代码的思路如下：首先创建一个que用来存放正在访问的元素，将根节点root放入到队列中，之后进入循环，定义一个size记录队列的大小，同时在循环里定义一个vector用来记录每层的元素，这里一定要用固定大小size而不要用que.size（），因为que.size()是不断变化的，之后循环遍历每层元素，取出队头元素存入vector，再将这个队头的左右孩子入队即可。代码如下：

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        queue<TreeNode*> que;
        vector<vector<int>> result;
        if(root != NULL)
            que.push(root);
        while(!que.empty())
        {
            int size = que.size();
            vector<int> vec;
            while(size--)
            {
                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;
    }
};

? ? ? ? 当然，本题也可以使用递归法：开始列写递归三要素：

1、确定递归函数的参数和返回值：这里cur指针是必备的，同时还有结果容器result，树的深度depth也有用，代码如下：

void order(TreeNode* cur, vector<vector<int>>& result, int depth)

2、确定终止条件：如果遍历到最后一个了，那么指针就会为空，代码如下：

if (cur == nullptr) return;

3、确定单层递归的逻辑：如果此时结果二维数组的深度等于树高，说明这是新的一层，那么就向result中传入一个一维整型数组，接下来进入正题，将当前节点的值添加到对应深度的一维数组中，开始递归，左子树，深度+1，右子树，深度+1，代码如下：

if (result.size() == depth) result.push_back(vector<int>());
        result[depth].push_back(cur->val);
        order(cur->left, result, depth + 1);
        order(cur->right, result, depth + 1);

?????????完整的代码如下所示：

# 递归法
class Solution {
public:
    void order(TreeNode* cur, vector<vector<int>>& result, int depth)
    {
        if (cur == nullptr) return;
        if (result.size() == depth) result.push_back(vector<int>());
        result[depth].push_back(cur->val);
        order(cur->left, result, depth + 1);
        order(cur->right, result, depth + 1);
    }
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> result;
        int depth = 0;
        order(root, result, depth);
        return result;
    }
};

? ? ? ? ?这篇文章覆盖了有关二叉树遍历的所有内容，非常重要！