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

本文是承接 二叉树心法（纲领篇） 的第五篇文章，主要讲二叉树后序位置的妙用，复述下前文关于后序遍历的描述：

前序位置的代码只能从函数参数中获取父节点传递来的数据，而后序位置的代码不仅可以获取参数数据，还可以获取到子树通过函数返回值传递回来的数据。

那么换句话说，一旦你发现题目和子树有关，那大概率要给函数设置合理的定义和返回值，在后序位置写代码了。

其实二叉树的题目真的不难，无非就是前中后序遍历框架来回倒嘛，只要你把一个节点该做的事情安排好，剩下的抛给递归框架即可。

但是对于有的题目，不同的遍历顺序时间复杂度不同。尤其是这个后序位置的代码，有时候可以大幅提升算法效率。

我们再看看后序遍历的代码框架：

void traverse(TreeNode root) {
    traverse(root.left);
    traverse(root.right);
    // 后序代码的位置
    // 在这里处理当前节点
}

void traverse(TreeNode* root) {
    if (root == nullptr) return;
    
    traverse(root->left);
    traverse(root->right);
    
    // 后序代码的位置
    // 在这里处理当前节点
}

def traverse(root):
    if not root:
        return
    traverse(root.left)
    traverse(root.right)
    # 后序代码的位置
    # 在这里处理当前节点

func traverse(root *TreeNode) {
    if root == nil {
        return
    }
    traverse(root.Left)
    traverse(root.Right)
    // 后序代码的位置
    // 在这里处理当前节点
}

var traverse = function(root) {
    if (root === null) return;
    traverse(root.left);
    traverse(root.right);
    // 后序代码的位置
    // 在这里处理当前节点
}

看这个代码框架，你说什么情况下需要在后序位置写代码呢？

如果当前节点要做的事情需要通过左右子树的计算结果推导出来，就要用到后序遍历。

下面就讲一个经典的算法问题，可以直观地体会到后序位置的妙用。这是力扣第 1373 题「二叉搜索子树的最大键值和」，函数签名如下：

int maxSumBST(TreeNode root);

int maxSumBST(TreeNode* root);

def maxSumBST(root: TreeNode)

func maxSumBST(root *TreeNode) int {
}

var maxSumBST = function(root) {

};