LeetCode 1373. 二叉搜索子树的最大键值和

Categories:

题目描述
思路分析
1. 解法一：后序 DFS（推荐）
相似题目

题目描述

✅ 1373. 二叉搜索子树的最大键值和

思路分析

解法一：后序 DFS（推荐）

核心思路：

后序遍历返回四元组：是否 BST、子树最小值、最大值、子树和。

若左右子树都是 BST 且满足 left.max < node.val < right.min，则当前为 BST。

维护全局最大 BST 子树和。

复杂度分析：

时间复杂度：O(n)，其中 n 表示节点数。

空间复杂度：O(h)，递归栈空间。

class Solution {
    private int best = 0;

    public int maxSumBST(TreeNode root) {
        dfs(root);
        return best;
    }

    private int[] dfs(TreeNode node) {
        if (node == null) {
            return new int[]{1, Integer.MAX_VALUE, Integer.MIN_VALUE, 0};
        }

        int[] left = dfs(node.left);
        int[] right = dfs(node.right);

        if (left[0] == 1 && right[0] == 1 && node.val > left[2] && node.val < right[1]) {
            int sum = left[3] + right[3] + node.val;
            best = Math.max(best, sum);
            int min = Math.min(left[1], node.val);
            int max = Math.max(right[2], node.val);
            return new int[]{1, min, max, sum};
        }

        return new int[]{0, 0, 0, 0};
    }
}

func maxSumBST(root *TreeNode) int {
	best := 0
	var dfs func(*TreeNode) (bool, int, int, int)

	dfs = func(node *TreeNode) (bool, int, int, int) {
		if node == nil {
			return true, 1<<30, -1<<30, 0
		}

		lb, lmin, lmax, lsum := dfs(node.Left)
		rb, rmin, rmax, rsum := dfs(node.Right)

		if lb && rb && node.Val > lmax && node.Val < rmin {
			sum := lsum + rsum + node.Val
			if sum > best {
				best = sum
			}
			minv := lmin
			if node.Val < minv {
				minv = node.Val
			}
			maxv := rmax
			if node.Val > maxv {
				maxv = node.Val
			}
			return true, minv, maxv, sum
		}

		return false, 0, 0, 0
	}

	dfs(root)
	return best
}

相似题目

题目	难度	考察点
1373. 二叉搜索子树的最大键值和	困难	树形 DP
98. 验证二叉搜索树	中等	BST
333. 最大二叉搜索子树	中等	树形 DP
124. 二叉树中的最大路径和	困难	树形 DP
543. 二叉树的直径	简单	树形 DP

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2024/41290626