代码随想录算法训练营第十四天 |二叉树理论基础、递归遍历、迭代遍历

题目链接：

leetcode 144.二叉树的前序遍历

leetcode 194.二叉树的中序遍历

leetcode 145.二叉树的后序遍历

文章讲解：代码随想录二叉树理论基础、递归遍历、迭代遍历、统一迭代法

二叉树的遍历问题是很经典很基础的问题，这里只总结我学习过程中认为是重点关注的内容，相信对大家理解遍历方式以及自己动手写这个代码会有帮助！

我学习中只关注了递归法和统一迭代法，因为我认为不统一的迭代法性价比不高。

递归法
递归法很简单，注意递归的终止条件即可，递归也是写代码比较基础核心的思想，我认为掌握递归的核心要领就是掌握好终止条件，这个自己要好好体会。

以下代码对比来看。

递归法代码（前序遍历）：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    //递归法 实现函数
    void preTraversal (TreeNode* node, vector<int>& result) {
        //终止条件
        if (node == nullptr) return ;
        //前序遍历
        result.push_back(node -> val);
        preTraversal(node -> left, result);
        preTraversal(node -> right, result);
        return ;
    }

    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> result;
        preTraversal(root, result);
        return result;
    }
};

递归法代码（中序遍历）：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    //递归法 实现函数
    void inTraversal (TreeNode* node, vector<int>& result) {
        //终止条件
        if (node == nullptr) return ;
        //中序遍历
        inTraversal(node -> left, result);
        result.push_back(node -> val);
        inTraversal(node -> right, result);
        return ;
    }

    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> result;
        inTraversal(root, result);
        return result;
    }
};

递归法代码（后序遍历）：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    //递归法 实现函数
    void postTraversal (TreeNode* node, vector<int>& result) {
        //终止条件
        if (node == nullptr) return ;
        //后序遍历
        postTraversal(node -> left, result);
        postTraversal(node -> right, result);
        result.push_back(node -> val);
        return ;
    }

    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> result;
        postTraversal(root, result);
        return result;
    }
};

统一迭代法
思路就是用栈进行遍历，其实函数递归在底层也是用栈来实现的，当我们不用递归而是自己用栈的时候，对于二叉树遍历的核心解决方式并没有改变。

这个方法重点就是首先确认好访问节点和处理节点两个概念。

我们规定访问节点就是指当前指针走到了这个节点，不做处理操作，处理节点才是把当前指针走到的节点输出（在题目中就是放到结果容器中）。不好解释，自己好好体会一下

然后要注意的就是，我们如何利用栈遍历二叉树，首先栈式先入后出，假设要进行前序遍历，前序遍历式中左右，放入栈里的顺序就要是右左中，然后如何确定要处理节点了呢？那就是用空指针打标记。

每次循环访问栈顶元素时，如果遇到了空指针就说明要处理节点了，把空指针pop掉，再取栈顶元素，处理一下，再pop掉。

以下代码对比查看
统一迭代法（前序遍历）：

//统一迭代法
class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        stack<TreeNode*> st;
        vector<int> result;
        //root先放进去
        if (root != nullptr) st.push(root);
        //思路是，按照顺序将对应节点放入栈中，注意要反着顺序放，因为栈是先入后出，然后给要处理的节点用空指针打标记
        while (!st.empty()) {
            //取出栈顶
            TreeNode* cur = st.top();
            if (cur != nullptr) {
                //这里就是访问的节点（遍历到的节点），访问到就先把该节点从栈中pop掉
                st.pop();
                //然后通过向栈中放入元素决定，什么时候处理节点
                //前序遍历原本是中左右，放入栈里就要放右左中
                //确定有子节点才放入
                if (cur -> right) st.push(cur -> right);
                if (cur -> left) st.push(cur -> left);
                //中指的是处理该节点，所以用空指针打标记
                st.push(cur);
                st.push(nullptr);
            } else {
                //走到这里说明遇到了标记，要处理标记前的节点了
                st.pop();
                cur = st.top();
                result.push_back(cur -> val);
                st.pop();
            }
        }
        return result;
    }
};

统一迭代法（中序遍历）：

//统一迭代法
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        stack<TreeNode*> st;
        vector<int> result;
        //root先放进去
        if (root != nullptr) st.push(root);
        //思路是，按照顺序将对应节点放入栈中，注意要反着顺序放，因为栈是先入后出，然后给要处理的节点用空指针打标记
        while (!st.empty()) {
            //取出栈顶
            TreeNode* cur = st.top();
            if (cur != nullptr) {
                //这里就是访问的节点（遍历到的节点），访问到就先把该节点从栈中pop掉
                st.pop();
                //然后通过向栈中放入元素决定，什么时候处理节点
                //中序遍历原本是左中右，放入栈里就要放右中左
                //确定有子节点才放入
                if (cur -> right) st.push(cur -> right);
                //中指的是处理该节点，所以用空指针打标记
                st.push(cur);
                st.push(nullptr);
                if (cur -> left) st.push(cur -> left);
            } else {
                //走到这里说明遇到了标记，要处理标记前的节点了
                st.pop();
                cur = st.top();
                result.push_back(cur -> val);
                st.pop();
            }
        }
        return result;
    }
};

统一迭代法（后序遍历）：

//统一迭代法
class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        stack<TreeNode*> st;
        vector<int> result;
        //root先放进去
        if (root != nullptr) st.push(root);
        //思路是，按照顺序将对应节点放入栈中，注意要反着顺序放，因为栈是先入后出，然后给要处理的节点用空指针打标记
        while (!st.empty()) {
            //取出栈顶
            TreeNode* cur = st.top();
            if (cur != nullptr) {
                //这里就是访问的节点（遍历到的节点），访问到就先把该节点从栈中pop掉
                st.pop();
                //然后通过向栈中放入元素决定，什么时候处理节点
                //后序遍历原本是左右中，放入栈里就要放中右左
                //中指的是处理该节点，所以用空指针打标记
                st.push(cur);
                st.push(nullptr);
                //确定有子节点才放入
                if (cur -> right) st.push(cur -> right);
                if (cur -> left) st.push(cur -> left);
            } else {
                //走到这里说明遇到了标记，要处理标记前的节点了
                st.pop();
                cur = st.top();
                result.push_back(cur -> val);
                st.pop();
            }
        }
        return result;
    }
};