LeetCode 333. 最大二叉搜索子树

Categories:

题目描述
思路分析
1. 解法一：后序遍历 + 子树信息合并（推荐）
相似题目

题目描述

✅ 333. 最大二叉搜索子树

思路分析

解法一：后序遍历 + 子树信息合并（推荐）

核心思路：

后序遍历在回溯时拿到左右子树信息：是否为 BST、节点数、最小值、最大值。

若左右子树均为 BST 且 left.max < root.val < right.min，当前子树仍是 BST，规模为左右之和加 1。

否则当前子树不是 BST，向上只需要返回左右子树中的最大 BST 规模。

复杂度分析：

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

空间复杂度：O(h)，其中 h 表示树高，递归栈占用。

class Solution {
    public int largestBSTSubtree(TreeNode root) {
        return dfs(root).size;
    }

    private Info dfs(TreeNode node) {
        if (node == null) {
            return new Info(true, 0, Long.MAX_VALUE, Long.MIN_VALUE);
        }

        Info left = dfs(node.left);
        Info right = dfs(node.right);

        // 判断当前子树是否仍为 BST
        if (left.isBst && right.isBst && node.val > left.max && node.val < right.min) {
            long min = Math.min(left.min, node.val);
            long max = Math.max(right.max, node.val);
            return new Info(true, left.size + right.size + 1, min, max);
        }

        int best = Math.max(left.size, right.size);
        return new Info(false, best, 0, 0);
    }

    private static class Info {
        boolean isBst;
        int size;
        long min;
        long max;

        Info(boolean isBst, int size, long min, long max) {
            this.isBst = isBst;
            this.size = size;
            this.min = min;
            this.max = max;
        }
    }
}

func largestBSTSubtree(root *TreeNode) int {
	return dfsLargest(root).size
}

type bstInfo struct {
	isBst bool
	size  int
	min   int
	max   int
}

func dfsLargest(node *TreeNode) bstInfo {
	if node == nil {
		return bstInfo{isBst: true, size: 0, min: maxInt(), max: minInt()}
	}

	left := dfsLargest(node.Left)
	right := dfsLargest(node.Right)

	// 判断当前子树是否仍为 BST
	if left.isBst && right.isBst && node.Val > left.max && node.Val < right.min {
		minVal := left.min
		if node.Val < minVal {
			minVal = node.Val
		}

		maxVal := right.max
		if node.Val > maxVal {
			maxVal = node.Val
		}

		return bstInfo{isBst: true, size: left.size + right.size + 1, min: minVal, max: maxVal}
	}

	best := left.size
	if right.size > best {
		best = right.size
	}

	return bstInfo{isBst: false, size: best, min: 0, max: 0}
}

func maxInt() int {
	return int(^uint(0) >> 1)
}

func minInt() int {
	return -maxInt() - 1
}

相似题目

题目	难度	考察点
98. 验证二叉搜索树	中等	二叉搜索树
230. 二叉搜索树中第K小的元素	中等	BST 中序
669. 修剪二叉搜索树	中等	BST 递归
700. 二叉搜索树中的搜索	简单	BST 查找
1373. 二叉搜索子树的最大键值和	困难	子树信息合并

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2021/60702983