C# iterative solution, no helper/global variables


  • -1
    M
    public int MaxPathSum(TreeNode root) {
        var leftMaxes = new Stack<int>();
        var sideMax = 0;
        int max = int.MinValue;
        
        var nodes = new Stack<TreeNode>();
        var states = new Stack<int>();
    
        nodes.Push(root);
        states.Push(0);
        
        while(nodes.Count > 0){
            var node = nodes.Peek();
            var state = states.Pop();
            
            if(node == null){
                nodes.Pop();
                sideMax = 0;
            }else if(state == 0){
                states.Push(1);
                nodes.Push(node.left);
                states.Push(0);
            }else if(state == 1){
                leftMaxes.Push(sideMax);
                states.Push(2);
                nodes.Push(node.right);
                states.Push(0);
            }else{
                int leftMax = Math.Max(leftMaxes.Pop(), 0);
                int rightMax = Math.Max(sideMax, 0);
                int pathMax = leftMax + rightMax + node.val;
                max = Math.Max(pathMax, max);
                sideMax = Math.Max(leftMax, rightMax) + node.val;
                nodes.Pop();
            }
        }
        
        return max;
    }

Log in to reply
 

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