O(n) AC Solution, in-order right child first iterative


  • 0
    I

    In-order iterative solution, right child first, then root, then left child; while visiting nodes, add past nodes' value to sum, add sum to current node value

    public TreeNode ConvertBST(TreeNode root) {
            var node = root;
            var sum = 0;
            var s = new Stack<TreeNode>();
            while(s.Count!=0 || node != null)
            {
                if(node != null)
                {
                    s.Push(node);
                    node = node.right;
                }
                else
                {
                    node = s.Pop();
                    var t = node.val;
                    node.val += sum;
                    sum += t;
                    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.