本文为博客:东哥带你刷二叉树(纲领篇) | labuladong 的算法笔记的笔记
前言
将二叉树的思想传递至动态规划,回溯算法,分治算法,图论算法!
对于二叉树的每一个结点,我们需要思考的是:如果单独抽出一个二叉树节点,它需要做什么事情?需要在什么时候(前/中/后序位置)做?
二叉树的重要性
拿快速排序和归并排序举例子
- 快速排序:二叉树的前序遍历(先确定p,再确定p的左面、p的右面)
- 归并排序:二叉树的后序遍历(确定左面数组、右面数组,对两部分数组进行合并)
只要涉及递归,都可以抽象成二叉树的问题 (学习完二叉树将继续更新动规,回溯等算法,我们先理解好二叉树的思想)
深入理解前中后序
再推一遍:东哥带你刷二叉树(纲领篇) | labuladong 的算法笔记,写的真的好orz
哈哈,反正我是中枪了~
下面分别给出二叉树、数组、链表遍历的框架,可以思考一下有哪些共同点:
单链表、数组可以递归访问,二叉树这种结构无非就是二叉链表 ,只是无法写成迭代遍历。
所谓前序位置,就是刚进入一个节点(元素)的时候,后序位置就是即将离开一个节点(元素)的时候(这句话非常重要,先从数组、链表的角度想)
举个例子,倒序打印链表元素,你会怎么写代码?用上述第三块代码,我们可以在后续位置添加print语句,即可!正序打印在前序位置添加语句即可。二叉树也是一样,二叉树具有前序位置,中序位置,后序位置,前中后序是遍历二叉树过程中处理每一个节点的三个特殊时间点(这句话堪称我一绝哈哈哈,请反复思考orz)
!!!标重点
前序位置的代码在刚刚进入一个二叉树节点的时候执行;
后序位置的代码在将要离开一个二叉树节点的时候执行;
中序位置的代码在一个二叉树节点左子树都遍历完,即将开始遍历右子树的时候执行。
这意味着什么?这意味着你只需要在这个框架上,往前序位置/中序/后序填你想要的代码就可以;这意味着你只需要考虑一个结点就可以(考虑刚刚进入这个节点该做什么,遍历完左子树需要做什么,离开这个节点需要做什么),再回头看二叉树,是不是清晰了很多。再补东哥一句话:你可以发现每个节点都有「唯一」属于自己的前中后序位置。
现在请小朋友回前言再看最后一句话,深思ing
两种解题思路
二叉树题目的递归解法可以分两类思路,第一类是遍历一遍二叉树得出答案,第二类是通过分解问题计算出答案,这两类思路分别对应着 回溯算法核心框架 和 动态规划核心框架。
回溯算法核心框架:没有返回值,靠更新外部变量来计算结果
动态规划核心框架:有返回值,返回值是子问题的计算结果
104. 二叉树的最大深度 - 力扣(LeetCode)再来看这道题,我们用两种写法来写一遍,并且解释为什么代码放在前序/中序/后序位置?
我们先来写回溯算法:
/**
* 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) {}
* };
*/
void traverse(TreeNode* root,int& depth,int& res){
if(root==nullptr){
return;
}
//前序位置
depth++;
if(depth>res){res=depth;cout<<res<<endl;}
traverse(root->left,depth,res);
//中序位置
traverse(root->right,depth,res);
//后序位置
depth--;
}
class Solution {
public:
int depth=0;
int res=0;
int maxDepth(TreeNode* root) {
traverse(root,depth,res);
return res;
}
};
干饭去了,朋友们~