代码随想录算法训练营打卡Day14 |LeetCode144 二叉树的前序遍历、LeetCode94 二叉树的中序遍历、LeetCode145 二叉树的后序遍历

摘要

二叉树的基础操作：前序、中序、后序遍历
迭代遍历性能较递归遍历好，但代码实现相对复杂

今日学习资料

代码随想录二叉树
数据结构C++语言版第二版（清华大学出版社）二叉树部分
王道考研数据结构复习指导二叉树部分

二叉树基础知识

二叉树的节点的定义

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) {}
 };

前序、中序、后序的“前”“中”“后”都指的是父节点相对于其左孩子和有孩子在遍历顺序中的位置。
前序、中序、后序的定义不在这里重复，以下以代码为主。

LeetCode144 二叉树的前序遍历

144. 二叉树的前序遍历 - 力扣（Leetcode）

递归法，最直观最容易理解的方法，用递归隐式维护了一个栈。

class Solution {
public:
    void preorderTraversalWorkPlace(TreeNode* node, vector<int>& res) {
        if (node == nullptr) {
            return;// 递归终止条件
        }
        res.push_back(node->val);
        preorderTraversalWorkPlace(node->left, res);
        preorderTraversalWorkPlace(node->right, res);
    }
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> res;
        preorderTraversalWorkPlace(root, res);
        return res;
    }
};

迭代法，前序遍历的迭代法是最容易实现的，因为在前序遍历中，对树的节点的访问顺序和处理顺序是相同的
- 访问顺序：通过cur访问树的节点的顺序
- 处理顺序：在这里，对树的节点的处理是取其中的值到保存遍历顺序的数组中
- 可以看出，在前序遍历中，只要
  1. 不断地取当前节点的值保存进答案数组，并将当前节点出栈
  2. 然后尝试将当前节点的右孩子和左孩子放入栈中，这里要注意栈的后进先出，前序遍历需要“中左右”，所以我们让右孩子先进栈。
  3. 实际上我们只需要用一个栈和一个临时保存已经弹出的栈顶元素的变量就可以完成前序遍历。前序遍历实际上只需要一个栈就可以完成。

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> res;
        stack<TreeNode*> s;
        if (root) {
            s.push(root);
        }
        TreeNode* cur;
        while (!s.empty()) {
            cur = s.top();
            s.pop();
            res.push_back(cur->val);

            if (cur->right) {
                s.push(cur->right);
            }
            if (cur->left) {
                s.push(cur->left);
            }
        }
        return res;
    }
};

LeetCode94 二叉树的中序遍历

递归法，由于不需要我们手动维护递归栈，递归法依然是最直观，最容易理解的方法

class Solution {
public:
    void inorderTraversalWorkPlace(TreeNode* node, vector<int>& res) {
        if (node == nullptr) {
            return;
        }
        inorderTraversalWorkPlace(node->left, res);
        res.push_back(node->val);
        inorderTraversalWorkPlace(node->right, res);
    }
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> res;
        inorderTraversalWorkPlace(root, res);
        return res;
    }
};

迭代法，这里体现出了中序遍历和前序遍历的区别，即在中序遍历中，对树的节点的访问顺序和处理顺序是不同的
- 访问顺序：实际上，我们对二叉树的访问顺序是基本固定的，即只能从父节点到左孩子或者右孩子
- 处理顺序：但在中序遍历中，我们要先取出的是左孩子，这自然与访问顺序有差别
- 所以，中序遍历不能只依靠一个栈来完成，而是要引入一个指针cur来先访问左孩子，并将访问过的左孩子保存在栈中，来调整对树的访问顺序。
  1. 用cur一直访问向左访问左孩子，直到左孩子为空，将cur指回当前栈顶的节点
  2. 中序遍历是“左中右”，既然当前cur已经没有左孩子或者左孩子已经处理过了，当前cur对应的是“中”，自然轮到cur指向的节点进行处理，然后栈顶元素出栈。
  3. 接下来轮到cur的右孩子，所以尝试让cur指向cur的右孩子，进入下一轮循环，尝试遍历“右”。

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> res;
        stack<TreeNode*> st;
        if (!root) {
            return res;
        }
        TreeNode* cur = root;
        while (cur || !st.empty()) {
            if (cur) {
                st.push(cur);
                cur = cur->left;
            }
            else {
                cur = st.top();
                st.pop();
                res.push_back(cur->val);
                cur = cur->right;
            }
        }
        return res;
    }
};

LeetCode145 二叉树的后序遍历

递归法

class Solution {
public:
    void postorderTraversalWorkPlace(TreeNode* node, vector<int>& res) {
        if (node == nullptr) {
            return;
        }
        postorderTraversalWorkPlace(node->left, res);
        postorderTraversalWorkPlace(node->right, res);
        res.push_back(node->val);
    }
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> res;
        postorderTraversalWorkPlace(root, res);
        return res;
    }
};

迭代法，遵守后序遍历的定义，对内存的进行“左右中”的有序访问
- 和中序遍历一样，后序遍历中，对树的元素访问顺序和处理顺序是不一致的，所以需要引入指针来调整访问顺序
- 和中序遍历相比，后序遍历为“左右中”，没有左孩子或左孩子已经处理完后，还要再访问一遍“中”才能去处理右孩子。处理完右孩子后，才轮到“中”进入遍历顺序，这意味着，在循环中会出现对“中”的重复访问。
- 所以，除了cur指针外，还要再引入一个pre指针来判断是否重复访问某个节点。
后序遍历“左右中”

先让cur一直尝试往左孩子走，并将cur访问过的节点保存在栈中，直到cur指向NULL。此时栈顶保存的节点没有左孩子，那么就剩下“右中”需要处理。
让cur指向栈顶保存的节点，并让栈顶节点出栈。然后处理“右”，如果当前节点没有右孩子，或者右孩子已经被访问过，则只剩下“中”，所以已经可以将当前节点加入遍历序列。
要记得将当前节点保存在pre中，作为下一个栈顶的节点判断右孩子是否已经访问过的依据。

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> res;
        if (!root) {
            return res;
        }
        stack<TreeNode*> st;
        TreeNode* cur = root;
        TreeNode* pre = nullptr;
        while (cur || !st.empty()) {
            while (cur) {
                st.push(cur);
                cur = cur->left;
            }
            cur = st.top();
            st.pop();
            if (cur->right == nullptr || cur->right == pre) {
                res.push_back(cur->val);
                pre = cur;
                cur = nullptr;
            }
            else {
                st.push(cur);
                cur = cur->right;
            }
        }
        return res;
    }
};

将前序遍历转化为后序遍历的迭代法
- 前序遍历是“中左右”，而后序遍历是“左右中”，所以
  1. 调整前序遍历中左孩子和右孩子的入栈顺序，先将左孩子入栈再将右孩子入栈，此时调整过的“前序遍历”为“中右左”
  2. 再将整个答案数组反转，就得到了“左右中”
  3. @Edward Elric 在 LeetCode 的官方题解的评论中指出，这样的方法只是得到了后序遍历的序列，但是并没有真正实现按后序遍历定义的顺序的内存访问。

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        stack<TreeNode*> st;
        vector<int> res;
        if (!root) {
            return res;
        }
        st.push(root);
        while (!st.empty()) {
            TreeNode* node = st.top();
            st.pop();
            res.push_back(node->val);
            if (node->left) st.push(node->left);
            if (node->right) st.push(node->right);
        }
        reverse(res.begin(), res.end());
        return res;
    }
};

image.png

更深一步的思考，是不是我们在迭代实现的思路中，没有用栈去很好地模拟函数的递归调用？顺着这个思路，即如何用栈来模拟二叉树遍历的递归实现，我在另一篇博客中分享了自己的理解。

统一代码形式的前序、中序、后序迭代法

C++统一形式迭代实现的前序、中序、后序遍历 - 简书 (jianshu.com)