O(n) solution with two traversal


  • 0
    S
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    public class Solution {
        int totalSum = 0;
        int incrementalSum = 0, temp;
        
        public TreeNode convertBST(TreeNode root) {
            traverseTree(root);
            traverseAgain(root);
            return root;
        }
        
        public void traverseTree(TreeNode root) {
            if (root == null)
                return;
            totalSum += root.val;
            traverseTree(root.left);
            traverseTree(root.right);
        }
        
        public void traverseAgain(TreeNode root) {
            if (root == null)
                return;
            traverseAgain(root.left);
            temp = root.val;
            root.val = totalSum - incrementalSum;
            incrementalSum += temp;
            traverseAgain(root.right);
        }
    }

Log in to reply
 

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