C# solution


  • 0
    B
    public class Result
    {
        public int min;
        public int max;
        public int size;
        public bool isValid;
    }
    public class Solution
    {
        public int LargestBSTSubtree(TreeNode root)
        {
            var result = GetPostOrder(root);
            if (result == null) return 0;
            return result.size;
        }
    
        public Result GetPostOrder(TreeNode root)
        {
            if (root == null)
                return null;
            var left = GetPostOrder(root.left);
            var right = GetPostOrder(root.right);
            Result result = null;
            if (left == null && right == null)
            {
                result = new Result { min = root.val, max = root.val, size = 1, isValid = true };
            }
            else if (left == null)
            {
                result = right.min > root.val && right.isValid ? new Result { size = right.size + 1, min = root.val, max = right.max, isValid = true } :
                         new Result { size = right.size, min = 0, max = 0, isValid = false };
            }
            else if (right == null)
            {
                result = left.max < root.val && left.isValid ? new Result { size = left.size + 1, min = left.min, max = root.val, isValid = true } :
                         new Result { size = left.size, min = 0, max = 0, isValid = false };
            }
            else if (left != null && right != null && left.isValid && right.isValid && left.max <= root.val && right.min > root.val)
            {
                result = new Result { size = left.size + right.size + 1, min = left.min, max = right.max, isValid = true };
            }
            else
            {
                result = new Result { size = Math.Max(left.size, right.size), min = 0, max = 0, isValid = false };
            }
            return result;
        }
    }
    

Log in to reply
 

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