把二叉搜索树转换为累加树

CSDN编程竞赛报名地址：https://edu.csdn.net/contest/detail/16
（请不要删掉此地址）

打卡!!!每日一题

今天给大家带来一道二叉搜索树类型的题目，对于二叉搜索树，根据其特性：

• 若它的左子树不空，则左子树上所有节点的值均小于它的根节点的值；
• 若它的右子树不空，则右子树上所有节点的值均大于它的根节点的值；
• 它的左、右子树也分别为二叉搜索树。

无非就是考察：中序遍历和反序中序遍历

中序遍历：即左根右的顺序遍历树结构，至此我们可以得到一个递增的序列
核心代码：

void dfs(TreeNode root){
    if(root==null){
        return;
    }
    dfs(root.left);
    print(root.val);
    dfs(root.right);
}
1
2
3
4
5
6
7
8

反序中序遍历：即右根左的顺序遍历树结构，我们可以得到一个递减的序列

void dfs(TreeNode root){
    if(root==null){
        return;
    }
    dfs(root.right);
    print(root.val);
    dfs(root.left);
}
1
2
3
4
5
6
7
8

好了，知道了这么多，我们基本可以在中等题目里横着走了，对，你没听错，对于二叉搜索树，就这么多知识点。

下面继续我们打卡的题目，这道题中等难度，我们看看到底难不难。

题目描述：538. 把二叉搜索树转换为累加树

给出二叉 搜索 树的根节点，该树的节点值各不相同，请你将其转换为累加树（Greater Sum Tree），使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。

提醒一下，二叉搜索树满足下列约束条件：

节点的左子树仅包含键 小于 节点键的节点。
节点的右子树仅包含键 大于 节点键的节点。
左右子树也必须是二叉搜索树。

题目示例：

说实话，我题目读完感觉出题人的表达能力还有很大的提升空间，明明那么简单的题目非要描述的那么凹口，可能出题人只能从题目描述上加大难度了。

我给大家翻译翻译：

它就是想让我们求树中大于等于该节点值的所有节点的总和，啥意思呢，比如题目示例1中4这个结点，那么我们需要相加的元素应该是全部大于等于4的，根据二叉搜索树的特性，我们只需全部遍历4的右子树，并且在遍历过程中将结点值相加得到的最后结果便是结点4的新值，大于等于4的值有：4,6,5,7,8，很明显全是其右子树的值。

最笨的办法就是我们遍历每个节点，然后依次求值就好

class Solution {
    int sum = 0;
    Map<TreeNode, Integer> map = new HashMap<>();

    public TreeNode convertBST(TreeNode root) {
        if (root == null) return root;
        if (root.left == null && root.right == null) return root;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            TreeNode temp = root;
            sum = 0;
            dfs(temp, node);
            if (node.left != null) {
                queue.add(node.left);
            }
            if (node.right != null) {
                queue.add(node.right);
            }
        }
        return root;
    }

    public void dfs(TreeNode root, TreeNode node) {
        if (root == null) return;
        dfs(root.right, node);
        if (map.containsKey(root)) {
            sum += map.get(root);
        } else {
            sum += root.val;
        }

        if (root == node) {
            map.put(root, root.val);
            root.val = sum;

            return;
        }
        dfs(root.left, node);
    }
}
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

但是呢，这样的话时间复杂度可能就比较高了，我们也不用怎么大刀阔斧的去改，我们可以判断这个节点我们曾经遍历过不，只要遍历过，就不需要在进行一次dfs了,于是我小改了一下，如下所示：

package com.exercise.leetecode.problem.剑指offer.深度and广度搜索;

import com.exercise.leetecode.common.TreeNode;
import org.springframework.util.CollectionUtils;

import java.util.*;

public class 把二叉搜索树转换为累加树_538 {
    int sum = 0;
    Map<TreeNode, Integer> map = new HashMap<>();
    Map<TreeNode, Integer> calMap = new HashMap<>();//保存每个计算之后的结点val值

    public TreeNode convertBST(TreeNode root) {
        if (root == null) return root;
        if (root.left == null && root.right == null) return root;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            TreeNode temp = root;
            if (calMap.containsKey(node)) {
                map.put(node, node.val);
                node.val = calMap.get(node);
            } else {
                sum = 0;
                dfs(temp, node);
            }
            if (node.left != null) {
                queue.add(node.left);
            }
            if (node.right != null) {
                queue.add(node.right);
            }
        }
        return root;
    }

    public void dfs(TreeNode root, TreeNode node) {
        if (root == null) return;
        dfs(root.right, node);
        if (map.containsKey(root)) {
            sum += map.get(root);
        } else {
            sum += root.val;
        }
        calMap.put(root, sum);
        if (root == node) {
            map.put(root, root.val);
            root.val = sum;

            return;
        }
        dfs(root.left, node);
    }
}

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
46
47
48
49
50
51
52
53
54
55
56

当然你还可以继续优化，就交给聪明的小伙伴啦。