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

题目链接

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

题目描述

注意点

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

解答思路

• 因为二叉搜索树的性质是左子树的值始终小于根节点的值，右子树的值始终大于根节点的值，对于任意一个节点，其右子树的累加和为右子树下节点的累加和，根节点的累加和为右子树的累加和再加上根节点的值，左子树的累加和为根节点的累加和再加上左子树下节点的累加和
• 本题是要找到比当前节点大于或等于的数值之和，其决定关系为右子树->根节点->左子树，所以本题使用反向中序遍历，也就是先遍历右子树，再遍历根节点，最后遍历左子树

代码

class Solution {
    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;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12

关键点

• 各节点的累加和的推理关系为右子树->根节点->左子树
• 递归遍历二叉树