Java non-recursive O(n) time


  • 0
    J
    public class Solution {
        public TreeNode convertBST(TreeNode root) {
            if(root==null) return null;
            TreeNode cur = root;
            int prevSum = 0;
            Stack<TreeNode> stack = new Stack<TreeNode>();
            while(!stack.isEmpty() || cur!=null){
                if(cur!=null){
                    stack.push(cur);
                    cur = cur.right;
                }
                else{
                    cur = stack.pop();
                    cur.val+=prevSum;
                    prevSum = 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.