二叉搜索树心法（后序篇）

1373. 二叉搜索子树的最大键值和 https://leetcode.cn/problems/maximum-sum-bst-in-binary-tree

1373. Maximum Sum BST in Binary Tree https://leetcode.com/problems/maximum-sum-bst-in-binary-tree

Info

已完成网站教程、网站习题、配套插件中所有多语言代码的校准，解决了之前 chatGPT 翻译可能出错的问题~

读完本文，你不仅学会了算法套路，还可以顺便解决如下题目：

LeetCode	Difficulty
1373. Maximum Sum BST in Binary Tree	🔴

Prerequisites

Before reading this article, you should learn:

• Basic Binary Tree Structure
• DFS/BFS Traversal of Binary Trees
• Dongge Takes You Through Binary Trees (Guideline)

This article is the fifth in the series following Dongge Takes You Through Binary Trees (Guideline), focusing on the clever uses of the post-order position in binary trees. Let's recap the previous description of post-order traversal:

Code in the pre-order position can only get data passed from the parent node through function parameters, while code in the post-order position can not only get parameter data but also data returned from the subtree through function return values.

In other words, if you notice that a problem involves subtrees, it's likely that you need to set a reasonable definition and return value for the function and write the code in the post-order position.

Actually, binary tree problems are not that hard. They mostly involve switching between pre-order, in-order, and post-order traversal frameworks. As long as you handle what a node should do, the rest can be left to the recursive framework.

However, for some problems, different traversal orders have different time complexities. Especially the code in the post-order position can sometimes significantly improve algorithm efficiency.

Let's take another look at the post-order traversal code framework:

java 🟢

void traverse(TreeNode root) {
    traverse(root.left);
    traverse(root.right);
    // the position of the post-order code
    // process the current node here
}

cpp 🤖

void traverse(TreeNode* root) {
    if (root == nullptr) return;
    
    traverse(root->left);
    traverse(root->right);
    
    // the position of post-order code
    // process the current node here
}

python 🤖

def traverse(root):
    if not root:
        return
    traverse(root.left)
    traverse(root.right)
    # position of post-order code
    # process the current node here

go 🤖

func traverse(root *TreeNode) {
    if root == nil {
        return
    }
    traverse(root.Left)
    traverse(root.Right)
    // the position of the post-order code
    // process the current node here
}

javascript 🤖

var traverse = function(root) {
    if (root === null) return;
    traverse(root.left);
    traverse(root.right);
    // the position of the post-order code
    // process the current node here
}

Look at this code framework. When do you think you need to write code in the post-order position?

If the task for the current node depends on the results from its left and right subtrees, you need to use post-order traversal.

Next, I'll explain a classic algorithm problem that clearly demonstrates the usefulness of the post-order position. This is LeetCode problem 1373, "Maximum Sum BST in Binary Tree," with the function signature as follows:

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) {

};

Problem Analysis

Thought Analysis

Optimization Strategy

Final Summary

loading...