# 333 Largest BST Subtree

Input: root node of a binary tree

output: find the size of the largest subtree which is a Binary Search Tree (BST)

Concept:

程式分成三部分:

  1. 主程式: 每圈要檢查root是否為null, 若left, right 都是null, return 1, 檢查root是不是合法BST(呼叫2), 如果是, 呼叫3, 算出root以下subtree的大小。recursive: 如果root不是valid,繼續檢查root下面的subtree,把自己的left child, right child丟進去跑,回傳Max(size(right),size(left))。
  2. 判斷此root以下是否為合法BST: 若root是null, 合法。若root不符合上下界,不合法。recursive: 把left, right再丟進去檢查,若left, right都valid,這個root才是valid。
  3. 計算此subtree的size: 若root是null,回傳0。若左右孩子都為null,回傳1。recursive: 將左右孩子丟進去跑,size(left)+size(right)+1即為此root的size

Pseudocode:

  1. largestBSTSubtree input: TreeNode
    output: 最大subtree的size
    if(root==null) return 0;
    if(left == null && right == null) return 1;
    if(isValid(root)) countNode(root);
    return Max(largestBSTSubtree(right),largestBSTSubtree(left));

  2. isValid
    input: TreeNode, min 下界, max 上界
    output: boolean
    if(root==null) return true;
    if(root.val <= min) return false;
    if(root.val >= max) return false;
    return isValid(right, root.val, max) && isValid(left, min, root.val)

  3. countNode
    input: TreeNode
    output: size of this subtree
    if(root==null) return 0;
    if(left==null && right == null) return 1;
    return countNode(left)+countNode(right)+1;

完整程式碼:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
    public class Solution {
        public int largestBSTSubtree(TreeNode root) {
        if (root == null) return 0;
        if (root.left == null && root.right == null) return 1;
        if (isValid(root, null, null)) return countNode(root);
        return Math.max(largestBSTSubtree(root.left), largestBSTSubtree(root.right));
    }

    public boolean isValid(TreeNode root, Integer min, Integer max) {
        if (root == null) return true;
        if (min != null && min >= root.val) return false;
        if (max != null && max <= root.val) return false;
        return isValid(root.left, min, root.val) && isValid(root.right, root.val, max);
    }

    public int countNode(TreeNode root) {
        if (root == null) return 0;
        if (root.left == null && root.right == null) return 1;
        return 1 + countNode(root.left) + countNode(root.right);
    }
}

results matching ""

    No results matching ""