代码随想录算法训练营第十三天 | 二叉树基础和深度优先遍历

二叉树基础

参考代码随想录的简介，这里我不仔细介绍了。

https://programmercarl.com/%E4%BA%8C%E5%8F%89%E6%A0%91%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE

二叉树的结构定义，利用链式存储：

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

对于二叉树的遍历，分为深度优先遍历和广度优先遍历两种。深度优先遍历进一步又可以分为前序遍历、中序遍历、后序遍历，可以采用递归或迭代方式来实现；广度优先遍历主要就是层次遍历，可用迭代方式来实现。

本篇中的递归和迭代遍历都是深度优先遍历。

二叉树的递归遍历

二叉树的递归遍历有三种，分别是前序遍历、中序遍历、后序遍历。

前序遍历：

void traversal(TreeNode* cur, vector<int>& vec) {
    if (cur == nullptr) 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 == nullptr) return;
    traversal(cur->left, vec);
    vec.push_back(cur->val);
    traversal(cur->right, vec);
}

后序遍历：

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

二叉树的迭代遍历

二叉树的迭代遍历也可以完成前序、中序、后序遍历，需要用栈来暂存二叉树的节点。

前序遍历是中左右的顺序。在进行前序遍历时，需要在访问完当前节点后，先把右孩子加入栈，再把左孩子加入栈，这样在出栈时正好是中左右的顺序。

前序遍历的迭代：

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        if(root == nullptr) return {};
        
        stack<TreeNode*> stk;
        vector<int> result;

        stk.push(root);

        while(!stk.empty()){
            TreeNode* cur = stk.top();
            stk.pop();
            result.push_back(cur->val);

            if(cur->right != nullptr){
                stk.push(cur->right);
            }
            if(cur->left != nullptr){
                stk.push(cur->left);
            }
        }

        return result;
    }
};

中序遍历的顺序是左中右，由于处理的节点和遍历的节点有些对不上，所以代码的逻辑是另一套。

中序遍历时需要先访问到当前子树的最左边，把路径中的节点都添加到栈里，当遍历到头时，将当前节点加入结果，再掉头指向右节点。需要借用指针的遍历来帮助访问节点，栈则用来处理节点上的元素。解释有点解释不清，代码如下：

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

后序遍历的顺序是左右中，对比先序遍历的顺序是中左右，那么只需要把先序遍历做一些略微的修改，变成中右左，再将结果反转就能够得到后序遍历了。

后序遍历的迭代版本如下：

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        if(root == nullptr) return {};
        vector<int> result;
        stack<TreeNode*> stk;
        stk.push(root);
        while(!stk.empty()){
            TreeNode* cur = stk.top();
            stk.pop();

            result.push_back(cur->val);
            if(cur->left != nullptr){
                stk.push(cur->left);
            }
            if(cur->right != nullptr){
                stk.push(cur->right);
            }
        }
        reverse(result.begin(), result.end());
        return result;
    }
};