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

2023-12-26 12:40:27

二叉树基础

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

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

文章来源:https://blog.csdn.net/weixin_43347688/article/details/135218248
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。