Standard preorder + inorder traversal


  • 0
    J

    The top solutions are ingenious.
    My initial thought was to calculate the sum of the entire BST, then starting from the leftest node, add the sum to every node following an inorder traversal.

    Overall running time is 2N ~ O(N) for N nodes

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

Log in to reply
 

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