Java intuitive O(n) solution


  • 0
    K
    public class Solution {
        public TreeNode convertBST(TreeNode root) {
            update(root, 0);
            return root;
        }
        
        private int update(TreeNode root, int prevBigger)
        {
            if(root == null) return 0;
            int alsoBigger = update(root.right, prevBigger);
            int smaller    = update(root.left, prevBigger+alsoBigger+root.val);
            
            int newVal = root.val + prevBigger + alsoBigger;
            int subtreeSum = smaller + root.val + alsoBigger;
            
            root.val = newVal;
            
            return subtreeSum;
        }
    }
    

Log in to reply
 

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