Iterative O(n) reverse in-order traversal with stack


  • 0

    '''
    public class Solution {
    public TreeNode convertBST(TreeNode root) {

        if(root == null) return root;
        
        Deque<TreeNode> stk = new ArrayDeque<>();
        TreeNode curr = root;
        int sum = 0;
        while( curr != null || !stk.isEmpty() )
        {
            while( curr != null)
            {
                stk.offer(curr);
                curr = curr.right;
            }
            curr = stk.pollLast();
            curr.val += sum;
            sum = curr.val;
            curr = curr.left;
        }
        return root;
    }
    

    }
    '''


Log in to reply
 

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