东哥带你刷二叉搜索树(后序篇)
原创数据结构二叉树分解问题的思路约 4035 字
Info
已完成网站教程、网站习题、配套插件中所有多语言代码的校准,解决了之前 chatGPT 翻译可能出错的问题~
读完本文,你不仅学会了算法套路,还可以顺便解决如下题目:
LeetCode | 力扣 | 难度 |
---|---|---|
1373. Maximum Sum BST in Binary Tree | 1373. 二叉搜索子树的最大键值和 | 🔴 |
本文是承接 东哥带你刷二叉树(纲领篇) 的第五篇文章,主要讲二叉树后序位置的妙用,复述下前文关于后序遍历的描述:
前序位置的代码只能从函数参数中获取父节点传递来的数据,而后序位置的代码不仅可以获取参数数据,还可以获取到子树通过函数返回值传递回来的数据。
那么换句话说,一旦你发现题目和子树有关,那大概率要给函数设置合理的定义和返回值,在后序位置写代码了。
其实二叉树的题目真的不难,无非就是前中后序遍历框架来回倒嘛,只要你把一个节点该做的事情安排好,剩下的抛给递归框架即可。
但是对于有的题目,不同的遍历顺序时间复杂度不同。尤其是这个后序位置的代码,有时候可以大幅提升算法效率。
我们再看看后序遍历的代码框架:
java 🟢
void traverse(TreeNode root) {
traverse(root.left);
traverse(root.right);
// 后序代码的位置
// 在这里处理当前节点
}
cpp 🤖
void traverse(TreeNode* root) {
if (root == nullptr) return;
traverse(root->left);
traverse(root->right);
// 后序代码的位置
// 在这里处理当前节点
}
python 🤖
def traverse(root):
if not root:
return
traverse(root.left)
traverse(root.right)
# 后序代码的位置
# 在这里处理当前节点
go 🤖
func traverse(root *TreeNode) {
if root == nil {
return
}
traverse(root.Left)
traverse(root.Right)
// 后序代码的位置
// 在这里处理当前节点
}
javascript 🤖
var traverse = function(root) {
if (root === null) return;
traverse(root.left);
traverse(root.right);
// 后序代码的位置
// 在这里处理当前节点
}
看这个代码框架,你说什么情况下需要在后序位置写代码呢?
如果当前节点要做的事情需要通过左右子树的计算结果推导出来,就要用到后序遍历。
下面就讲一个经典的算法问题,可以直观地体会到后序位置的妙用。这是力扣第 1373 题「二叉搜索子树的最大键值和」,函数签名如下:
java 🟢
int maxSumBST(TreeNode root);
cpp 🤖
int maxSumBST(TreeNode* root);
python 🤖
def maxSumBST(root: TreeNode)
go 🤖
func maxSumBST(root *TreeNode) int {
}
javascript 🤖
var maxSumBST = function(root) {
};