Leetcode 538.把二叉搜索树转换为累加树

题目描述：

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

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

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

示例 1：

1
2

输入：[4,1,6,0,2,5,7,null,null,null,3,null,null,null,8]
输出：[30,36,21,36,35,26,15,null,null,null,33,null,null,null,8]

示例 2：

1
2

输入：root = [0,null,1]
输出：[1,null,1]

示例 3：

1
2

输入：root = [1,0,2]
输出：[3,3,2]

示例 4：

1
2

输入：root = [3,2,4,1]
输出：[7,9,4,10]

提示：

• 树中的节点数介于 $0$ 和 $10^4$ 之间。
• 每个节点的值介于 $-10^4$ 和 $10^4$ 之间。
• 树中的所有值 互不相同 。
• 给定的树为二叉搜索树。

链接：

https://leetcode-cn.com/problems/convert-bst-to-greater-tree

题目分析

1.我的做法

  二叉搜索树的特点就是有序，如果按照中序遍历的顺序就可以得到升序序列，而题目中要求将节点的值更新为大于等于它的所有节点和，其实就是要进行中序遍历的逆序，并将节点值累加起来作为新节点值。
  中序遍历的逆序可以使用 DFS 来完成。我们传给一个节点的值就是上一个节点更新后的值。这个数可能来自父节点，也可能来自右孩子。那么我们使用一个参数 up 表示从上层（父节点）传过来的值，而返回值就是当前结点所表示的子树最左的节点值（最近更新的值）。
  遍历的顺序是 右中左。我们先遍历右子树，得到的返回值给自己更新，并将更新后的值传给左子树。而左子树的返回值才是我们要传给上层的返回值。
  比如示例 1 中，节点 6 将右子树 7 返回的 15 加到自己身上得到 21，然后把 21 传给左子树 5 进行更新，左子树更新后返回 26，节点 6 返回给上层的也是 26，表示这个子树累加的值是 26。然后节点 4 就可以根据节点 6 返回的 26 将自己更新为 30，继续传给左子树 1。而对于空的节点，我们则将 up 原封不动地返回去，这样就没有影响。

1
2
3
4
5
6
7
8
9
10
11
12

class Solution {
    int BFS(TreeNode* node, int up){
        if(node == nullptr) return up;
        node->val += BFS(node->right, up);
        return BFS(node->left, node->val);
    }
public:
    TreeNode* convertBST(TreeNode* root) {
        BFS(root, 0);
        return root;
    }
};

  时间复杂度：$O(n)$，其中 $n$ 是二叉搜索树的节点数。我们对二叉树做了一次中序遍历的逆序。
  空间复杂度：$O(n)$，其中 $n$ 是二叉搜索树的节点数。也就是 DFS 中栈的开销，最坏情况下深度为 $n$。

2.官方题解

  官方题解的第一个做法也是同样的思路，按照中序遍历的逆序遍历。不同的是，官方题解使用了一个类的成员变量（也就类似于全局变量）记录累加和，然后就没有多写一个 DFS 函数。当然这样也是一种方法，然后我在下面的评论区找到了和我做法一模一样的 Java 题解（还是十分有成就感的），那个人说这算是一种 code smell，就是尽量不要使用这样的全局变量，虽然对于这个题目来说全局变量无伤大雅，但是类内部的变量都这么无所谓的话，就变成一坨 shit 了。嗯很有道理。
  第二种方法是使用了 Morris 遍历的方法，大概就是说直接将前缀节点（右子树的最左子节点）连接到当前节点上，这样是利用了树中指向空的指针，所以是无需额外空间的，然后处理顺序就可以通过这个前缀节点进行。代码如下，我感觉很难讲出来具体操作，可以结合代码理解。

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

class Solution {
public:
    TreeNode* getSuccessor(TreeNode* node) {
        TreeNode* succ = node->right;
        while (succ->left != nullptr && succ->left != node) {
            succ = succ->left;
        }
        return succ;
    }

    TreeNode* convertBST(TreeNode* root) {
        int sum = 0;
        TreeNode* node = root;

        while (node != nullptr) {
            if (node->right == nullptr) {
                sum += node->val;
                node->val = sum;
                node = node->left;
            } else {
                TreeNode* succ = getSuccessor(node);
                if (succ->left == nullptr) {
                    succ->left = node;
                    node = node->right;
                } else {
                    succ->left = nullptr;
                    sum += node->val;
                    node->val = sum;
                    node = node->left;
                }
            }
        }

        return root;
    }
};