← Static tasks

333. Largest BST Subtree

leetcode medium

#backtracking#csharp#leetcode#math#medium#recursion#search#tree#two-pointers

Task

Дан корень бинарного дерева, найдите самое большое поддерево, которое также является деревом бинарного поиска (BST), где "самое большое" означает поддерево с наибольшим количеством узлов.

Дерево бинарного поиска (BST) — это дерево, в котором все узлы соблюдают следующие свойства:

Значения в левом поддереве меньше значения их родительского (корневого) узла.

Значения в правом поддереве больше значения их родительского (корневого) узла.

Примечание: Поддерево должно включать всех своих потомков.

Пример:

Input: root = [10,5,15,1,8,null,7]

Output: 3

Explanation: The Largest BST Subtree in this case is the highlighted one. The return value is the subtree's size, which is 3.

C# solution

matched/original
public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int x) { val = x; }
}
public class NodeValue {
    public int minNode, maxNode, maxSize;
    
    public NodeValue(int minNode, int maxNode, int maxSize) {
        this.minNode = minNode;
        this.maxNode = maxNode;
        this.maxSize = maxSize;
    }
}
public class Solution {
    private NodeValue largestBSTSubtreeHelper(TreeNode root) {
        if (root == null) {
            return new NodeValue(int.MaxValue, int.MinValue, 0);
        }
        
        NodeValue left = largestBSTSubtreeHelper(root.left);
        NodeValue right = largestBSTSubtreeHelper(root.right);
        
        if (left.maxNode < root.val && root.val < right.minNode) {
            return new NodeValue(Math.Min(root.val, left.minNode), Math.Max(root.val, right.maxNode), 
                                 left.maxSize + right.maxSize + 1);
        }
        
        return new NodeValue(int.MinValue, int.MaxValue, Math.Max(left.maxSize, right.maxSize));
    }
    
    public int LargestBSTSubtree(TreeNode root) {
        return largestBSTSubtreeHelper(root).maxSize;
    }
}

C++ solution

auto-draft, review before submit
#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int x) { val = x; }
}
public class NodeValue {
    public int minNode, maxNode, maxSize;
    
    public NodeValue(int minNode, int maxNode, int maxSize) {
        this.minNode = minNode;
        this.maxNode = maxNode;
        this.maxSize = maxSize;
    }
}
class Solution {
public:
    private NodeValue largestBSTSubtreeHelper(TreeNode root) {
        if (root == null) {
            return new NodeValue(int.MaxValue, int.MinValue, 0);
        }
        
        NodeValue left = largestBSTSubtreeHelper(root.left);
        NodeValue right = largestBSTSubtreeHelper(root.right);
        
        if (left.maxNode < root.val && root.val < right.minNode) {
            return new NodeValue(min(root.val, left.minNode), max(root.val, right.maxNode), 
                                 left.maxSize + right.maxSize + 1);
        }
        
        return new NodeValue(int.MinValue, int.MaxValue, max(left.maxSize, right.maxSize));
    }
    
    public int LargestBSTSubtree(TreeNode root) {
        return largestBSTSubtreeHelper(root).maxSize;
    }
}

Java solution

matched/original
class NodeValue {
    public int maxNode, minNode, maxSize;
    
    NodeValue(int minNode, int maxNode, int maxSize) {
        this.maxNode = maxNode;
        this.minNode = minNode;
        this.maxSize = maxSize;
    }
};

class Solution {
    public NodeValue largestBSTSubtreeHelper(TreeNode root) {
        if (root == null) {
            return new NodeValue(Integer.MAX_VALUE, Integer.MIN_VALUE, 0);
        }
        
        NodeValue left = largestBSTSubtreeHelper(root.left);
        NodeValue right = largestBSTSubtreeHelper(root.right);
        
        if (left.maxNode < root.val && root.val < right.minNode) {
            return new NodeValue(Math.min(root.val, left.minNode), Math.max(root.val, right.maxNode), 
                                left.maxSize + right.maxSize + 1);
        }
        
        return new NodeValue(Integer.MIN_VALUE, Integer.MAX_VALUE, 
                            Math.max(left.maxSize, right.maxSize));
    }
    
    public int largestBSTSubtree(TreeNode root) {
        return largestBSTSubtreeHelper(root).maxSize;
    }
}

JavaScript solution

matched/original
class TreeNode {
    constructor(val = 0, left = null, right = null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

class NodeValue {
    constructor(minNode, maxNode, maxSize) {
        this.minNode = minNode;
        this.maxNode = maxNode;
        this.maxSize = maxSize;
    }
}

var largestBSTSubtreeHelper = function(root) {
    if (root === null) {
        return new NodeValue(Number.MAX_SAFE_INTEGER, Number.MIN_SAFE_INTEGER, 0);
    }
    
    let left = largestBSTSubtreeHelper(root.left);
    let right = largestBSTSubtreeHelper(root.right);
    
    if (left.maxNode < root.val && root.val < right.minNode) {
        return new NodeValue(Math.min(root.val, left.minNode), Math.max(root.val, right.maxNode), 
                             left.maxSize + right.maxSize + 1);
    }
    
    return new NodeValue(Number.MIN_SAFE_INTEGER, Number.MAX_SAFE_INTEGER, Math.max(left.maxSize, right.maxSize));
};

var largestBSTSubtree = function(root) {
    return largestBSTSubtreeHelper(root).maxSize;
};

Python solution

matched/original
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class NodeValue:
    def __init__(self, minNode, maxNode, maxSize):
        self.minNode = minNode
        self.maxNode = maxNode
        self.maxSize = maxSize

class Solution:
    def largestBSTSubtreeHelper(self, root: TreeNode) -> NodeValue:
        if not root:
            return NodeValue(float('inf'), float('-inf'), 0)
        
        left = self.largestBSTSubtreeHelper(root.left)
        right = self.largestBSTSubtreeHelper(root.right)
        
        if left.maxNode < root.val < right.minNode:
            return NodeValue(min(root.val, left.minNode), max(root.val, right.maxNode), 
                             left.maxSize + right.maxSize + 1)
        
        return NodeValue(float('-inf'), float('inf'), max(left.maxSize, right.maxSize))
    
    def largestBSTSubtree(self, root: TreeNode) -> int:
        return self.largestBSTSubtreeHelper(root).maxSize

Go solution

matched/original
import "math"

type TreeNode struct {
    Val int
    Left *TreeNode
    Right *TreeNode
}

type NodeValue struct {
    minNode, maxNode, maxSize int
}

func largestBSTSubtreeHelper(root *TreeNode) NodeValue {
    if root == nil {
        return NodeValue{math.MaxInt64, math.MinInt64, 0}
    }
    
    left := largestBSTSubtreeHelper(root.Left)
    right := largestBSTSubtreeHelper(root.Right)
    
    if left.maxNode < root.Val && root.Val < right.minNode {
        return NodeValue{min(root.Val, left.minNode), max(root.Val, right.maxNode), 
                         left.maxSize + right.maxSize + 1}
    }
    
    return NodeValue{math.MinInt64, math.MaxInt64, max(left.maxSize, right.maxSize)}
}

func largestBSTSubtree(root *TreeNode) int {
    return largestBSTSubtreeHelper(root).maxSize
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

Explanation

Algorithm

Пост-упорядоченный обход дерева:

Обходите каждую ноду дерева в пост-упорядоченном порядке (left-right-root). Это позволит гарантировать, что обе поддеревья ноды уже проверены на соответствие критериям BST перед проверкой самой ноды.

Проверка условий BST для каждой ноды:

Для каждой ноды определите минимальное и максимальное значения в её левом и правом поддеревьях. Проверьте, удовлетворяет ли текущее поддерево условиям BST:

- значение текущей ноды должно быть больше максимального значения в левом поддереве.

- значение текущей ноды должно быть меньше минимального значения в правом поддереве.

Если условия выполняются, вычислите размер текущего поддерева как сумму размеров левого и правого поддеревьев плюс 1 (для текущей ноды).

Возврат максимального размера BST:

Если текущее поддерево не является BST, верните максимальный размер BST из его левого или правого поддерева.

В конце рекурсивного обхода верните максимальный размер BST в дереве.

😎