Java O(n) recursive solution


  • 0
    L

    helper function returns the sum of the current subtree.

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

Log in to reply
 

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