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

发布时间:2024年01月10日

题目链接:

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