Share my 1ms Java code


  • 0
    Z

    /**
    * @see Largest BST Subtree,
    * valid if current node is a BST, if so, return the node number,
    * else, return left child and right child's max node number.
    * we need a new class to define if the tree is a BST or not
    * @param root
    * @return
    */
    public int largestBSTSubtree(TreeNode root) {
    return validBST(root, Integer.MIN_VALUE, Integer.MAX_VALUE).maxNode;
    }

    public NodeData validBST(TreeNode root, int low, int high) {
        if(root == null) return new NodeData(true, 0);
        // check if the current node meet the requirement
        if(root.val < high && root.val >= low) {
        	// if left node is a BST and his max node
        	NodeData left = validBST(root.left, low, root.val);
        	NodeData right = validBST(root.right, root.val, high);
        	// if left child and right child is BST, return true and total node
            if(left.isBST && right.isBST) {
                return new NodeData(true, 1 + left.maxNode + right.maxNode);
            }else{
            	// if one of the child is not BST, calculate the max of their child, return false
            	int max = Math.max(validBST(root.left, Integer.MIN_VALUE, Integer.MAX_VALUE).maxNode, 
            			validBST(root.right, Integer.MIN_VALUE, Integer.MAX_VALUE).maxNode);
                return new NodeData(false, max);
            }
        }else{
            return new NodeData(false, -1);
        }
    }
    
    public class NodeData {
    	
    	public NodeData(boolean isBST, int maxNode) {
    		this.isBST = isBST;
    		this.maxNode = maxNode;
    	}
    	
    	public boolean isBST;
    	public int maxNode;
    	
    }

Log in to reply
 

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