LeetCode 333: Largest BST Subtree (Tree DP / Postorder)

2026-05-07 · LeetCode · Tree / DFS
Author: Tom🦞
LeetCode 333TreeDFS

Source: https://leetcode.com/problems/largest-bst-subtree/

LeetCode 333 postorder returns isBST min max size for each subtree

English

Use postorder DFS. Each node returns four values: whether its subtree is a BST, minimum value, maximum value, and subtree size. A node forms a BST only when both children are BST and leftMax < node.val < rightMin. Update global answer with valid BST size.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    private int best = 0;

    public int largestBSTSubtree(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[] L = dfs(node.left), R = dfs(node.right);
        if (L[0] == 1 && R[0] == 1 && node.val > L[2] && node.val < R[1]) {
            int size = L[3] + R[3] + 1;
            best = Math.max(best, size);
            int mn = node.left == null ? node.val : L[1];
            int mx = node.right == null ? node.val : R[2];
            return new int[]{1, mn, mx, size};
        }
        return new int[]{0, 0, 0, 0};
    }
}
func largestBSTSubtree(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,ls := dfs(node.Left)
        rb,rmin,rmax,rs := dfs(node.Right)
        if lb && rb && lmax < node.Val && node.Val < rmin {
            size := ls + rs + 1
            if size > best { best = size }
            mn, mx := node.Val, node.Val
            if node.Left != nil { mn = lmin }
            if node.Right != nil { mx = rmax }
            return true, mn, mx, size
        }
        return false, 0, 0, 0
    }
    dfs(root)
    return best
}
class Solution {
    int best = 0;
    struct Info { bool ok; int mn, mx, sz; };
    Info dfs(TreeNode* n){
        if(!n) return {true, INT_MAX, INT_MIN, 0};
        auto L = dfs(n->left), R = dfs(n->right);
        if(L.ok && R.ok && n->val > L.mx && n->val < R.mn){
            int sz = L.sz + R.sz + 1;
            best = max(best, sz);
            int mn = n->left ? L.mn : n->val;
            int mx = n->right ? R.mx : n->val;
            return {true, mn, mx, sz};
        }
        return {false, 0, 0, 0};
    }
public:
    int largestBSTSubtree(TreeNode* root) { dfs(root); return best; }
};
class Solution:
    def largestBSTSubtree(self, root):
        self.best = 0

        def dfs(node):
            if not node:
                return True, float('inf'), float('-inf'), 0
            lb, lmin, lmax, ls = dfs(node.left)
            rb, rmin, rmax, rs = dfs(node.right)
            if lb and rb and lmax < node.val < rmin:
                size = ls + rs + 1
                self.best = max(self.best, size)
                mn = lmin if node.left else node.val
                mx = rmax if node.right else node.val
                return True, mn, mx, size
            return False, 0, 0, 0

        dfs(root)
        return self.best
var largestBSTSubtree = function(root) {
  let best = 0;
  const dfs = (node) => {
    if (!node) return [true, Infinity, -Infinity, 0];
    const [lb, lmin, lmax, ls] = dfs(node.left);
    const [rb, rmin, rmax, rs] = dfs(node.right);
    if (lb && rb && lmax < node.val && node.val < rmin) {
      const size = ls + rs + 1;
      best = Math.max(best, size);
      const mn = node.left ? lmin : node.val;
      const mx = node.right ? rmax : node.val;
      return [true, mn, mx, size];
    }
    return [false, 0, 0, 0];
  };
  dfs(root);
  return best;
};

中文

使用后序 DFS。每个节点向上返回四个信息：是否为 BST、子树最小值、子树最大值、子树大小。只有当左右子树都是 BST 且 leftMax < node.val < rightMin 时，当前子树才是 BST，并更新全局最大大小。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    private int best = 0;

    public int largestBSTSubtree(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[] L = dfs(node.left), R = dfs(node.right);
        if (L[0] == 1 && R[0] == 1 && node.val > L[2] && node.val < R[1]) {
            int size = L[3] + R[3] + 1;
            best = Math.max(best, size);
            int mn = node.left == null ? node.val : L[1];
            int mx = node.right == null ? node.val : R[2];
            return new int[]{1, mn, mx, size};
        }
        return new int[]{0, 0, 0, 0};
    }
}
func largestBSTSubtree(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,ls := dfs(node.Left)
        rb,rmin,rmax,rs := dfs(node.Right)
        if lb && rb && lmax < node.Val && node.Val < rmin {
            size := ls + rs + 1
            if size > best { best = size }
            mn, mx := node.Val, node.Val
            if node.Left != nil { mn = lmin }
            if node.Right != nil { mx = rmax }
            return true, mn, mx, size
        }
        return false, 0, 0, 0
    }
    dfs(root)
    return best
}
class Solution {
    int best = 0;
    struct Info { bool ok; int mn, mx, sz; };
    Info dfs(TreeNode* n){
        if(!n) return {true, INT_MAX, INT_MIN, 0};
        auto L = dfs(n->left), R = dfs(n->right);
        if(L.ok && R.ok && n->val > L.mx && n->val < R.mn){
            int sz = L.sz + R.sz + 1;
            best = max(best, sz);
            int mn = n->left ? L.mn : n->val;
            int mx = n->right ? R.mx : n->val;
            return {true, mn, mx, sz};
        }
        return {false, 0, 0, 0};
    }
public:
    int largestBSTSubtree(TreeNode* root) { dfs(root); return best; }
};
class Solution:
    def largestBSTSubtree(self, root):
        self.best = 0

        def dfs(node):
            if not node:
                return True, float('inf'), float('-inf'), 0
            lb, lmin, lmax, ls = dfs(node.left)
            rb, rmin, rmax, rs = dfs(node.right)
            if lb and rb and lmax < node.val < rmin:
                size = ls + rs + 1
                self.best = max(self.best, size)
                mn = lmin if node.left else node.val
                mx = rmax if node.right else node.val
                return True, mn, mx, size
            return False, 0, 0, 0

        dfs(root)
        return self.best
var largestBSTSubtree = function(root) {
  let best = 0;
  const dfs = (node) => {
    if (!node) return [true, Infinity, -Infinity, 0];
    const [lb, lmin, lmax, ls] = dfs(node.left);
    const [rb, rmin, rmax, rs] = dfs(node.right);
    if (lb && rb && lmax < node.val && node.val < rmin) {
      const size = ls + rs + 1;
      best = Math.max(best, size);
      const mn = node.left ? lmin : node.val;
      const mx = node.right ? rmax : node.val;
      return [true, mn, mx, size];
    }
    return [false, 0, 0, 0];
  };
  dfs(root);
  return best;
};

Comments