C# - post order traversal using bottom up recursion


  • 2
        // data object to add to bottom up result or signal invalid subtree 
        public class BSTNode
        {
            public bool isBST = false;
            public int min = 0;
            public int max = 0;
            public int count = 0;
        }
    
        public class Solution
        {
            public static BSTNode TrueNode = new BSTNode() { isBST = true, count = 0, min = 0, max = 0 };
            public static BSTNode FalseNode = new BSTNode() { isBST = false, count = 0, min = 0, max = 0 };
            int best = 0;
            
            public int LargestBSTSubtree(TreeNode root)
            {
                best = 0;
                Find(root);
                return best;
            }
    
            public BSTNode Find(TreeNode node)
            {
                if (node == null) return TrueNode;
                
                BSTNode left = Find(node.left);
                BSTNode right = Find(node.right);
                
                if (left == FalseNode || right == FalseNode) return FalseNode;
    
                if ((left.count == 0 || node.val > left.max) && (right.count == 0 || node.val < right.min))
                {
                    int curr = 1 + left.count + right.count;
                    best = curr > best ? curr : best;
                    
                    return new BSTNode() 
                    { 
                        isBST = true, 
                        count = curr, 
                        min = (left.count == 0 ? node.val : left.min),
                        max = (right.count == 0 ? node.val : right.max)
                    };
                }
                else
                {
                    return FalseNode;
                }
            }
        }
        
    
    

Log in to reply
 

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