C# - iterative single pass


  • 0

    traverse the tree in reverse in-order, and tally the sum and update the nodes during visit step.

        public TreeNode ConvertBST(TreeNode root) {
            TreeNode node = root;
            Stack<TreeNode> stack = new Stack<TreeNode>();
            
            int sum = 0;
            while (node != null || stack.Count > 0)
            {
                if (node != null)
                {
                    stack.Push(node);
                    node = node.right;
                }
                else
                {
                    // visit
                    node = stack.Pop();
                    sum += node.val;
                    node.val = sum;
                    
                    node = node.left;
                }
            }
            
            return root;
        }
    

Log in to reply
 

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