首页 > 编程语言 >代码随想录算法训练营第11天|二叉树part01

代码随想录算法训练营第11天|二叉树part01

时间:2024-08-18 20:52:15浏览次数:13  
标签:11 遍历 TreeNode 随想录 st right 二叉树 left result

理论基础

需要了解 二叉树的种类,存储方式,遍历方式 以及二叉树的定义

二叉树纯理论方面还是比较简单,以前都学过,没什么可讲的。满二叉树就是满了,完全二叉树就是层满了(而且是左边)。平衡二叉搜索树就是左右深度绝对值差1。一般采用链式存储方式,顺序存储结构如果父节点的数组下标是 i,那么它的左孩子就是 i * 2 + 1,右孩子就是 i * 2 + 2。

遍历方式,前序遍历,中序遍历,和后序遍历(前中后是中间遍历的顺序)

以后续遍历。还是比较简单,左右中。看着下面的表一学就会。

546
5412678
456
1425768
465
1247865

二叉树的定义如下,还是和链表非常像的。一个值,两个左右节点指针。加上一个构造函数(基于传入的数x),默认的左右指针为空。

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

文章讲解: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

补充下迭代和递归的区别:

1. 迭代 (Iteration)

迭代是一种重复执行代码块的过程,通常使用循环结构(如 for 循环或 while 循环)来实现。在每次迭代中,代码块被多次执行,直到满足某个条件停止循环。

特点

  • 状态显式管理:循环中的变量(如计数器或指针)用于追踪进度,明确管理循环的状态。
  • 效率高:迭代在大多数情况下比递归更节省内存和时间,因为递归调用会有函数调用的开销。
  • 无栈溢出风险:迭代不会像递归那样面临栈溢出问题,尤其是在处理大量数据时。

2. 递归 (Recursion)

  1. 递归是一种函数调用自身的编程技术,通过不断地将问题分解为更小的子问题,直到遇到最基本的情况(基准情况),此时递归终止。

    特点

  2. 自然分治:递归非常适合解决那些可以分解为更小问题的任务,如树形结构遍历、动态规划、分治法等。
  3. 代码简洁:递归可以使得代码更易读,特别是在处理复杂的算法(如快速排序、归并排序、斐波那契数列)时。
  4. 有栈溢出风险:由于递归使用系统栈,每次递归调用都会占用栈空间,过多的递归调用可能导致栈溢出。

核心还是递归要使用系统栈,迭代不用,所以迭代效率高点。方法上:递归调用自己本身,迭代基于循环。

递归遍历 (必须掌握)

每次写递归,都按照这三要素来写,可以保证大家写出正确的递归算法!

  1. 确定递归函数的参数和返回值: 确定哪些参数是递归的过程中需要处理的,那么就在递归函数里加上这个参数, 并且还要明确每次递归的返回值是什么进而确定递归函数的返回类型。

  2. 确定终止条件: 写完了递归算法, 运行的时候,经常会遇到栈溢出的错误,就是没写终止条件或者终止条件写的不对,操作系统也是用一个栈的结构来保存每一层递归的信息,如果递归没有终止,操作系统的内存栈必然就会溢出。

  3. 确定单层递归的逻辑: 确定每一层递归需要处理的信息。在这里也就会重复调用自己来实现递归的过程

二叉树的三种递归遍历掌握其规律后,其实很简单 以下给的是前序遍历,如果是中序和后序只要改下顺序即可。  if (cur == NULL) return;开头一定要判断下终止条件。

class Solution {
public:
    void traversal(TreeNode* cur, vector<int>& vec) {//传入指针遍历数和要存储的数组
        if (cur == NULL) 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;
    }
};

题目链接/文章讲解/视频讲解:https://programmercarl.com/%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E9%80%92%E5%BD%92%E9%81%8D%E5%8E%86.html

迭代遍历 (基础不好的录友,迭代法可以放过)

题目链接/文章讲解/视频讲解:https://programmercarl.com/%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E8%BF%AD%E4%BB%A3%E9%81%8D%E5%8E%86.html

前序遍历代码如下
class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        stack<TreeNode*> st;
        vector<int> result;
        if (root == NULL) return result;
        st.push(root);
        while (!st.empty()) {
            TreeNode* node = st.top();                       // 中
            st.pop();
            result.push_back(node->val);
            if (node->right) st.push(node->right);           // 右(空节点不入栈)
            if (node->left) st.push(node->left);             // 左(空节点不入栈)
        }
        return result;
    }
};

前序遍历迭代法还是挺简单,第一步把根节点压入进去堆栈,把根节点值压入result数组中,然后根据根节点,压入右子节点指针,和左子节点指针,这样按照顺序弹出,只要栈里不为空,一直谈。弹出一个指针,但是又把他的右左子节点指针弹出,除非没有左右子结点,当堆栈为空时,就遍历完了。

以该图为例。

前序遍历中序遍历后序遍历

栈st,5右,5左

result 5

栈:指向5

result 空

栈st,5右,4右,4左

result 5, 4

栈:指向5,5左

result 空

栈st,5右,4右,

result 5, 4,1

栈:指向5,4左

result 空

result 5, 4,1,2

st,6右,6左

栈:指向5,

result 1,4

st,5右,

result 5, 4,1,2,6

栈:指向5,4右

result 1,4,2

栈st,6右

result 5, 4,1,2,6,7

栈:

result 1,4,2,5

栈st,空

result 5, 4,1,2,6,7,8

栈:5右,

result 1,4,2,5,

栈:5右,6左

result 1,4,2,5,

栈:5右,

result 1,4,2,5,7

栈:6右

result 1,4,2,5,7,6

栈:

result 1,4,2,5,7,6,8

另外一定别忘了判断,空指针本质上也是个指针。空指针(nullptr)可以被压入栈中。在 C++ 中,空指针只是一个特殊的指针值,表示该指针不指向任何有效的内存地址。空指针在本质上仍然是一个指针,只是其值为 nullptr(在现代 C++ 中)或 NULL(在早期 C++ 中)。

题目链接/文章讲解:https://programmercarl.com/%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E7%BB%9F%E4%B8%80%E8%BF%AD%E4%BB%A3%E6%B3%95.html

中序遍历

中序遍历最大的问题还是高清思路,第一步,先访问到最左底层,把遇到的统统压入栈中之后处理,当到最后一层后,再往下是空指针,进入else,把原先最左边的值导入到结果中,然后看看它右边有咩有,有的话继续循环,没有的话就跳出来,收拾上一个。只要弹出来的,立刻压倒结果里,然后,指向右指针,右指针有遍历右指针,没有就跳出来。

/**
 * 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:
    vector<int> inorderTraversal(TreeNode* root) {
{
    TreeNode*cur=root;
    stack<TreeNode*>st;
    vector<int>result;
    while(!st.emoty||cur!=NULL){
        if(cur!=NULL)
        {
            st.push(cur);
            cur=cur->left;
        }
        else
        {
            cur=st.top();
            st.pop();
            result.push_back(cur->val);     // 中
            cur = cur->right;               // 右
        }
    }
    return result;
    }
};
后序遍历

我在想为什么后序遍历是基于前序遍历,而不可以中序遍历,想想也明白了。因为中序遍历本质上一直是二分法,左边和右边,左边的就给我放入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:
    vector<int> postorderTraversal(TreeNode* root) {
stack<TreeNode*> st;
        vector<int> result;
        if (root == NULL) return result;
        st.push(root);
        while (!st.empty()) {
            TreeNode* node = st.top();
            st.pop();
            result.push_back(node->val);
            if (node->left) st.push(node->left); // 相对于前序遍历,这更改一下入栈顺序 (空节点不入栈)
            if (node->right) st.push(node->right); // 空节点不入栈
        }
        reverse(result.begin(), result.end()); // 将结果反转之后就是左右中的顺序了
        return result;
    }
};

统一迭代

标记法:将访问的节点放入栈中,把要处理的节点也放入栈中但是要做标记,就是要处理的节点放入栈之后,紧接着放入一个空指针作为标记。 

感觉还是比较好理解,相当于正常遍历。按照顺序遍历,

栈里面,右半部分,中,空指针,左半部分

先弹出左边一部分,继续压进去,左半部分的右半部分,左半部分的中,空指针,左半部分的左半部分

弹出来发现下面时空,这时候就该返回了,返回返回返回,且只返回中间值。完成目标。真是太巧妙了

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> result;
        stack<TreeNode*> st;
        if (root != NULL) st.push(root);
        while (!st.empty()) {
            TreeNode* node = st.top();
            if (node != NULL) {
                st.pop(); // 将该节点弹出,避免重复操作,下面再将右中左节点添加到栈中
                if (node->right) st.push(node->right);  // 添加右节点(空节点不入栈)

                st.push(node);                          // 添加中节点
                st.push(NULL); // 中节点访问过,但是还没有处理,加入空节点做为标记。

                if (node->left) st.push(node->left);    // 添加左节点(空节点不入栈)
            } else { // 只有遇到空节点的时候,才将下一个节点放进结果集
                st.pop();           // 将空节点弹出
                node = st.top();    // 重新取出栈中元素
                st.pop();
                result.push_back(node->val); // 加入到结果集
            }
        }
        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:
    vector<vector<int>> levelOrder(TreeNode* root) {
        queue<TreeNode*>que;

        if(root!=nullptr)
        que.push(root);
        vector<vector<int>>result;
        while(!que.empty())
        {

            int size=que.size();
            vector<int>vec;
            for(int i=0;i<size;i++){
                TreeNode *temp=que.front();
                que.pop();
                vec.push_back(temp->val);
                if(temp->left)
                que.push(temp->left);
                if(temp->right)
                que.push(temp->right);   
            }
        result.push_back(vec);
        }
        return result; 
    }
};

题目链接/文章讲解/视频讲解:https://programmercarl.com/0102.%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E5%B1%82%E5%BA%8F%E9%81%8D%E5%8E%86.html

标签:11,遍历,TreeNode,随想录,st,right,二叉树,left,result
From: https://blog.csdn.net/zxjiaya/article/details/141287585

相关文章

  • 代码随想录算法训练营第10天|栈与队列part02
    150.逆波兰表达式求值本题不难,但第一次做的话,会很难想到,所以先看视频,了解思路再去做题classSolution{public:intevalRPN(vector<string>&tokens){stack<longlong>st;for(conststring&token:tokens){if(token=="+......
  • 代码随想录Day17
    654.最大二叉树给定一个不重复的整数数组nums。最大二叉树可以用下面的算法从nums递归地构建:创建一个根节点,其值为nums中的最大值。递归地在最大值左边的子数组前缀上构建左子树。递归地在最大值右边的子数组后缀上构建右子树。返回nums构建的最大二叉树......
  • 【代码随想录训练营第42期 Day32打卡 - 从零开始动态规划 - LeetCode 509. 斐波那契数
    目录一、做题心得二、动规五步走三、题目与题解题目一:509.斐波那契数题目链接题解1:记忆性递归 题解2:动态规划题目二:70.爬楼梯 题目链接题解:动态规划题目三:746.使用最小花费爬楼梯题目链接题解:动态规划三、小结一、做题心得今天开始动态规划章节的第一......
  • 诗|随想——202311-12月的一些絮絮叨叨
    诗|随想——202311-12月的一些絮絮叨叨20231122随想01茫然随想02平和20231122随想03活着随想04爱随想05呓语20231123随想06失去随想07朦胧随想08成长随想09爱你20231124随想10掌控随想11秘密随想12我记得20231125随想13你我随想14祈盼随想15生命......
  • [LeetCode] 1367. Linked List in Binary Tree 二叉树中的链表
    Givenabinarytree root anda linkedlistwith head asthefirstnode.ReturnTrueifalltheelementsinthelinkedliststartingfromthe head correspondtosome downwardpath connectedinthebinarytree otherwisereturnFalse.Inthiscontext......
  • 代码随想录算法训练营第十五天
    力扣题部分:110.平衡二叉树题目链接:.-力扣(LeetCode)题面:        给定一个二叉树,判断它是否是平衡二叉树        平衡二叉树 是指该树所有节点的左右子树的深度相差不超过1思路(递归):还是递归三部曲(关于三部曲的具体内容和对递归看法建议可见昨......
  • 代码随想录算法训练营第十八天
    力扣题部分:530.二叉搜索树的最小绝对差题目链接:.-力扣(LeetCode)题面:给你一个二叉搜索树的根节点 root ,返回 树中任意两不同节点值之间的最小差值 。差值是一个正数,其数值等于两值之差的绝对值。思路:    写关于二叉搜索树的问题,一定要先掌握二叉搜索树......
  • 2024.8.11至2024.8.17周总结
    本周学习任务清单1.字符串:Hash、KMP、trie树、拓展KMP(Z函数)、AC自动机、Manacher、回文自动机、后缀数组、后缀自动机、广义后缀自动机2.数论:欧拉函数、莫比乌斯函数、欧拉反演、莫比乌斯反演、筛法、杜教筛、min25筛3.博弈论:公平组合游戏、反常游戏、SG函数总结本周学习的......
  • 雷达气象学(11)——双偏振雷达的相态识别与降水估测
    目录11.1相态识别的原理11.2相态识别算法11.3降水估测的原理11.1相态识别的原理在上一篇文章我们已经知道,不同类别的水凝物在双偏振雷达上表现出不同的特性,因此可以根据双偏振雷达观测推测出水凝物的相态类型,或者说推测出回波的类型。具体而言,是利用双偏振变量如\(Z_{DR}\)......
  • [C++ Error] f0201.cpp(11): E2379 Statement missing ;
    错误解释:这个错误表明在C++源代码文件f0201.cpp的第11行出现了一个语法错误,具体是缺少了一个分号;。C++语言规定语句的结束需要使用分号;,如果一个语句缺少了它,编译器就会抛出这样的错误。解决方法:打开f0201.cpp文件``,定位到第11行。检查那一行的代码,确保每个语句后面都有分号;......