Java bottom-up (post-order) recursive solution


  • 0
    D
    public class Solution {
        public int largestBSTSubtree(TreeNode root) {
            return calcNodeInfo(root).maxNodes;
        }
        
        private NodeInfo calcNodeInfo(TreeNode root) {
            NodeInfo me = new NodeInfo();
            if (root == null) {
                return me;
            }
            NodeInfo left = calcNodeInfo(root.left);
            NodeInfo right = calcNodeInfo(root.right);
            
            me.isBST = left.isBST && right.isBST && (left.maxVal == null || left.maxVal < root.val)
                    && (right.minVal == null || right.minVal > root.val);
            me.nodes = 1 + left.nodes + right.nodes;
            me.maxVal = right.maxVal == null ? root.val : right.maxVal;
            me.minVal = left.minVal == null ? root.val : left.minVal;
            me.maxNodes = me.isBST ? me.nodes : Math.max(left.maxNodes, right.maxNodes);
            
            return me;
        }
        
        class NodeInfo {
            boolean isBST = true;
            int nodes;
            Integer maxVal;
            Integer minVal;
            int maxNodes;
        }
    }
    

Log in to reply
 

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