Share my Java O(n) solution! Very easy to understand


  • 6
    public class Solution {
        class Signal {
            int min = Integer.MAX_VALUE;
            int max = Integer.MIN_VALUE;
            boolean flag = true;
            int num = 0;
        }
        public int largestBSTSubtree(TreeNode root) {
            // O(n) complexity
            if (root == null) {
                return 0;
            }
            Signal signal = helper(root);
            return signal.num;
        }
        private Signal helper(TreeNode root) {
            Signal signal = new Signal();
            if (root == null) {
                return signal;
            } else if (root.left == null && root.right == null) {
                signal.num = 1;
                signal.min = root.val;
                signal.max = root.val;
                return signal;
            }
            Signal left = helper(root.left);
            Signal right = helper(root.right);
            if (left.flag == false || right.flag == false) {
                signal.num = Math.max(left.num,right.num);
                signal.flag = false;
                return signal;
            } else {
                if (root.val > left.max && root.val < right.min) {
                    signal.min = Math.min(left.min,root.val);
                    signal.max = Math.max(right.max,root.val);
                    signal.num = left.num + right.num + 1;
                    return signal;
                } else {
                    signal.num = Math.max(left.num, right.num);
                    signal.flag = false;
                    return signal;
                }
            }
        }
    }

  • 1
    C

    You can use num to replace the flag somehow.


  • 0

    @monkeyGoCrazy Great solution. Here's a mildly refactored version of your code:

        static class Node {
            int min = Integer.MAX_VALUE; 
            int max = Integer.MIN_VALUE; 
            boolean isBST = true; 
            int subtreeSize = 0;      
        }
        
        public int largestBSTSubtree(TreeNode root) {
            if (root == null) return 0;
            Node node = dfs(root);
            return node.subtreeSize;
        }
        
        private Node dfs(TreeNode root) {
            Node node = new Node();
            if (root == null) return node;
            if (root.left == null && root.right == null) {
                // leaf node
                node.min = node.max = root.val; node.subtreeSize = 1;
                return node;
            }
            Node left = dfs(root.left);
            Node right = dfs(root.right);
            if (!isBST(left, right, root)) {
                node.isBST = false; 
                node.subtreeSize = Math.max(left.subtreeSize, right.subtreeSize);
            } else {
                node.subtreeSize = 1 + left.subtreeSize + right.subtreeSize;
                node.min = Math.min(left.min, root.val); node.max = Math.max(right.max, root.val);
            }
            return node;
        }
        
        private boolean isBST(Node left, Node right, TreeNode root) {
            return left.isBST && right.isBST && root.val >= left.max && root.val <= right.min;
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.