One traverse java solution


  • 0
    L
    public TreeNode convertBST(TreeNode root) {
            TreeNode cur = root;
            Stack<TreeNode> stack = new Stack<>();
            
            int runningSum = 0;
            while (!stack.isEmpty() || cur != null){
                if (cur != null){
                    stack.push(cur);
                    cur = cur.right;
                }else{
                    cur = stack.pop();
                    runningSum += cur.val;
                    cur.val += (runningSum - cur.val);
                    cur = cur.left;
                }
            }
            
            return root;
        }

Log in to reply
 

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