333. Largest BST Subtree

LeetCode medium original: C# #backtracking #csharp #leetcode #math #medium #recursion #search #tree #two-pointers

선택한 UI 언어에 맞게 문제 텍스트를 러시아어에서 번역합니다. 코드는 변경하지 않습니다.

LeetCode Static

Дан корень бинарного дерева, find самое большое под트리, которое также является 트리м бинарного поиска (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# 해법

매칭됨/원본

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++ 해법

자동 초안, 제출 전 검토

#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 해법

매칭됨/원본

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 해법

매칭됨/원본

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 해법

매칭됨/원본

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 해법

매칭됨/원본

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
}

Algorithm

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

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

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

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

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

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

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

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

Если текущее под트리 не является BST, return maximum размер BST из его левого или правого поддерева.

В конце рекурсивного обхода return maximum размер BST в дереве.

😎

Vacancies for this task

활성 채용 with overlapping task tags are 표시됨.

전체 채용

아직 활성 채용이 없습니다.