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

要求

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

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

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

工具类

public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
         this.val = val;
         this.left = left;
         this.right = right;
     }
}
1
2
3
4
5
6
7
8
9
10
11
12

---

---

思路

对如下只有三个节点的搜索二叉树而言，计算结果就是，右子节点保持不变，中间节点的值是其本身与右子节点相加的和，左子节点的值是其本身与中间节点、右子节点三者的累计之和。

若求中间节点的值，必须要先遍历完右子节点；而若求左子节点的值，必须要遍历完中间节点和右子节点。因此，我们只需要进行一次反向中序遍历（即遍历顺序为右子树–>根节点–>左子树），在遍历过程中需要将已经遍历的节点的值进行累加，然后再赋值给当前节点。

1、 定义一个全局变量sum，用于存储遍历的所有节点值的累计和；
2、递归终止条件： root为空就返回null;
3、递归右子树root.right;
4、遍历当前节点，作如下操作：
———将其值累加到sum中；
———把sum赋值给当前节点的值；
5、递归左子树root.left;

public class LeetCode538 {
    int sum = 0;
    public TreeNode convertBST(TreeNode root) {
        //递归终止条件
        if (root == null) {
            return null;
        }
        //递归到最右子节点位置，从下往上遍历
        convertBST(root.right);
        //算出当前节点值+sum的值，再把sum赋值给当前节点
        sum += root.val;
        root.val = sum;
        convertBST(root.left);
        return root;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16