leetcode/src/HOT100/Main538.java at master · codinglin/leetcode · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
package HOT100;

public class Main538 {
    int sum = 0;

    public TreeNode convertBST(TreeNode root) {
        sum = sumNode(root);
        prefixNode(root);
        return root;
    }

    private int sumNode(TreeNode root){
        if(root==null){
            return 0;
        }
        int left = sumNode(root.left);
        int right = sumNode(root.right);
        return left + right+ root.val;
    }

    private void prefixNode(TreeNode root){
        if(root==null){
            return;
        }
        int sub = root.val;
        root.val = sum;
        sum -= sub;
        prefixNode(root.left);
        prefixNode(root.right);
    }
}

class Main538_1 {
    int sum = 0;

    public TreeNode convertBST(TreeNode root) {
        if(root != null){
            convertBST(root.right);
            sum += root.val;
            root.val = sum;
            convertBST(root.left);
        }
        return root;
    }
}