share my divide and conquer solution


  • 0
    I

    honestly, I am not quite sure the time complexity, anyone can help? O(n) i think

    public class Solution {
        public int largestBSTSubtree(TreeNode root) {
            if (root == null) {
                return 0;
            }
            int total = isValid(Integer.MIN_VALUE, root, Integer.MAX_VALUE); 
            return (total != -1) ? total : Math.max(largestBSTSubtree(root.left), largestBSTSubtree(root.right));
        }
        private int isValid(int min, TreeNode root, int max) {
            if (root == null) {
                return 0;
            }
            int left = isValid(min, root.left, root.val);
            int right = isValid(root.val, root.right, max);
            if (root.val <= min || root.val >= max) {
                return -1;
            }
            return (left == -1 || right == -1) ? -1 : left + right + 1; 
        }
    }
    

Log in to reply
 

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