Java Recursive O(n) time


  • 33

    Since this is a BST, we can do a reverse inorder traversal to traverse the nodes of the tree in descending order. In the process, we keep track of the running sum of all nodes which we have traversed thus far.

    public class Solution {
    
        int sum = 0;
        
        public TreeNode convertBST(TreeNode root) {
            convert(root);
            return root;
        }
        
        public void convert(TreeNode cur) {
            if (cur == null) return;
            convert(cur.right);
            cur.val += sum;
            sum = cur.val;
            convert(cur.left);
        }
        
    }
    

  • 21

    Recursive version not using global variable.

    public TreeNode convertBST(TreeNode root) {
        dfs(root, 0);
        return root;
    }
    public int dfs(TreeNode root, int val) {
        if(root == null) return val;
        int right = dfs(root.right, val);
        int left = dfs(root.left, root.val + right);
        root.val = root.val + right;
        return left;
    }

  • 2

    @compton_scatter Here's one that doesn't use a global variable:

        public TreeNode convertBST(TreeNode root) {
            if (root == null) return null;
            int[] rightVal = new int[1];
            reverseInorder(root, rightVal);
            return root;
        }
        
        private void reverseInorder(TreeNode root, int[] rightVal) {
            if (root == null) return;
            
            reverseInorder(root.right, rightVal);
            root.val = root.val + rightVal[0];
            rightVal[0] = root.val;
            reverseInorder(root.left, rightVal);
        }
    

  • 6

    here's the iterative version which also doesn't use a global var.

        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
                {
                    node = stack.Pop();
                    sum += node.val;
                    node.val = sum;
                    
                    node = node.left;
                }
            }
            
            return root;
        }
    

  • 0
    Y
    This post is deleted!

  • 1

    I came up with the following rewrite, which don't have to depend on class member ("global") variable.

    public class ConvertBST2GreaterTree {
    	
    	public TreeNode convertBST(TreeNode root) {
    		convert(root, 0);
            	return root;
        	}
    	private static int convert(TreeNode node,  int sum){
    		if(node==null) return sum;
    		sum = convert(node.right, sum);
    		sum+=node.val;
    		node.val = sum;
    		return convert(node.left, sum);
    	}
    }
    

  • 0
    R

    This is simply amazing. I wasted time building a table to hold sums till end . Saves a linear inorder scan by doing reverse inorder !


  • 0

    Crystal clear!


  • 9

    @jaqenhgar Maybe it's more like inorder traversal written in this way. :)

        public TreeNode convertBST(TreeNode root) {
            dfs(root, 0);
            return root;
        }
        
        // sum   : all nodes which we have traversed thus far
        // return: root.val + sum of all nodes greater than root
        private int dfs(TreeNode root, int sum) {
            if (root == null) return sum;
            int rsum = dfs(root.right, sum);
            root.val += rsum;
            return dfs(root.left, root.val);
        }
    

  • 0
    This post is deleted!

  • 2
    G

    wondering why the accepted solution all assume the simple case when the BST has no duplicates


  • 1
    Y

    a "reversed" version of inorder traversal. right --> root --> left.

    public class Solution {
        /**
         * @param root the root of binary tree
         * @return the new root
         */
        public TreeNode convertBST(TreeNode root) {
            // Write your code here
            int sum = 0; 
            helper(root, sum);
            return root;
        }
        
        public int helper(TreeNode root, int sum) {
            if (root == null) {
                return sum;
            }
            int right = helper(root.right, sum);
            root.val += right;
            int left = helper(root.left, root.val);
            
            return left;
        }
         
    }
    

  • 0
    K

    public class Solution {
    public TreeNode convertBST(TreeNode root) {
    if(root==null) return null;
    helper(root,0);
    return root;
    }

    int helper(TreeNode root, int sum){
        if(root==null) return sum;
        if(root.left==null && root.right==null){
            root.val=root.val+sum;
            return root.val;
        }
        int right = helper(root.right,sum);
        root.val +=right;
        int left= helper(root.left, root.val);
        return left;
    }
    

    }


  • 0
    L
    A solution with no helper
    public class Solution {
        public int excess = 0;
        //traverse with the order of R D L
        public TreeNode convertBST(TreeNode root) {
            if (root == null) {
                return null;
            }
            convertBST(root.right);
            
            root.val += excess ;
            excess = root.val;
            
            convertBST(root.left);
            return root; 
        }
        
    }
    

  • 0
    T
    public TreeNode convertBST(TreeNode root) {
        convertBSTHelper(root, 0);
        return root;
    }
    public int convertBSTHelper(TreeNode root, int sum) {
        if(root == null) return sum;
        root.val+=convertBSTHelper(root.right, sum); 
        return convertBSTHelper(root.left,root.val);
    }

  • 0
    I

    @compton_scatter This would modify the original Tree. Based on the method signature, author doesn't want to modify the original tree.
    Would need to first clone a tree and apply the algo on the clone tree, but this would require to traverse a tree twice.


  • 0
    N

    BST can have duplicate value which isn't considered as "greater". Thus need to take care of this

        private int sum=0;
        private int sum_pre =0;
        private int pre=0;
        public TreeNode convertBST(TreeNode root) {
            helper(root);
            return root;
        }
        private void helper(TreeNode node){
            if(node==null) return;
            helper(node.right);
            if(node.val==pre){
                sum+=pre;
                node.val += sum_pre;
            } else{
                sum_pre = sum;
                pre = node.val;
                sum+=node.val;
                node.val=sum;
            }
            helper(node.left);
        }
    

  • 0
    M

    @jdrogin hey man, why do you decide to use a Stack data structure for this?


Log in to reply
 

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