ConvertBSTTOGreaterTree [source code]

public class ConvertBSTTOGreaterTree {
static
/******************************************************************************/
public class Solution {
    public TreeNode convertBST(TreeNode root) {
        int[] sum = new int[1];
        sum[0] = 0;
        dfs(root, sum);
        return root;
    }

    private void dfs(TreeNode root, int[] sum) {
        if (root == null) return;
        dfs(root.right, sum);
        root.val += sum[0];
        sum[0] = root.val;
        dfs(root.left, sum);
    }
}
/******************************************************************************/

    public static void main(String[] args) {
        ConvertBSTTOGreaterTree.Solution tester = new ConvertBSTTOGreaterTree.Solution();
    }
}

Integer不能作为 accum, 还是传不上去; 最后还是只能用 array 来做;

就算不专门加一个 Empty Case 的处理, 至少脑子里要过一下, 或者让 OJ 过一下;

这个问题总体的思路并不困难, 还是抓住一个点, 就是 BST 里面, 如果你按照 DFS 做出的 traversal, 最后得到的顺序就是 sorted 的. 如果给你的是一个sorted array, 这个问题你就很好想: 从最右边最大的开始, 维护一个sum, 然后一直往左边走一遍就行了. 这里换成了 BST, 其实是一样的;

最后的速度是19ms (37%), 不算优秀;

这个题目其实recursive return value是可以做成一个TreeNode 的, 不过没有必要; 直接就用 void 的 mutation 来做就行了;

另外这里:

root.val += sum[0];  
sum[0] = root.val;

刚开始也是没有转过来弯, 想不到怎么更新这两个量的顺序; 这个的话, 自己纸上画两个数字算一下比你脑袋里干想要好很多;

这个是 submission 最优解:

public class Solution {  
    int sum = 0;  
    public TreeNode convertBST(TreeNode root) {        
        dfs(root);  
        return root;  
    }  
    public void dfs(TreeNode cur)  
    {  
        if(cur == null)  
            return;  
        if(cur.right != null)  
            dfs(cur.right);  
        sum = sum + cur.val;  
        cur.val = sum;  
        if(cur.left != null)  
            dfs(cur.left);  
    }  

}

其实本质的思路是非常类似的, 他这里的区别就是首先使用 global, 可见在 JAVA 里面使用instance var其实并不会造成多大的 overhead. 事实上, 是完全没有;
其次一点, 他实质上用一个 if 来避免了所有走向 null 的 call; 其实最后速度差距也没有那么大, 无所谓了;

public class Solution {  
    int sum = 0;  

    public TreeNode convertBST(TreeNode root) {  
        if (root == null) return null;  

        convertBST(root.right);  

        root.val += sum;  
        sum = root.val;  

        convertBST(root.left);  

        return root;  
    }  
}

这个是 discussion 上面一个没有 helper 的版本, 那么对应的, 他就必须要有一个recursive return value, which is TreeNode. 这个做法最后居然是最优解!!! 14(98). 这个还真是没有想到. 不过这个点子我还是想到了的;
可能是因为 Tree 的操作最后实际上操作的还是就是指针, 所以就算有返回值, 但是因为是一个mutable的返回值, 所以实际上的返回操作并不会造成太大的因为 alloc 造成的速度损失;

Problem Description

Given a Binary Search Tree (BST), convert it to a Greater Tree such that every key of the original BST is changed to the original key plus sum of all keys greater than the original key in BST.

Example:

Input: The root of a Binary Search Tree like this:
5
/ \
2 13

Output: The root of a Greater Tree like this:
18
/ \
20 13
Difficulty:Easy
Total Accepted:11.8K
Total Submissions:22.3K
Contributor: love_Fawn
Companies
amazon
Related Topics
tree