Java Solution using in-order traversal


  • 0
    S
    public class Solution {
        Map<Integer, TreeNode> map = new HashMap<>();
        List<Integer> order = new ArrayList<>();
        int sum = 0;
        public TreeNode convertBST(TreeNode root) {
            inOrder(root);
        
            int count=0;
            for(int i:order){
                count += i;
                map.get(i).val += sum-count;
            }
        
            return root;
        }
    
        private void inOrder(TreeNode root){
            if(root==null)
                return;
        
            inOrder(root.left);
            sum += root.val;
            order.add(root.val);
            map.put(root.val, root);
            inOrder(root.right);
        }
    }

Log in to reply
 

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