Rabbet

悦已者

0%

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

发表于 更新于 分类于
本文字数： 1.2k 阅读时长 ≈ 1 分钟
(BST问题 ＃538)

题目描述

给出二叉搜索树的根节点，该树的节点值各不相同，请你将其转换为累加树(Greater Sum Tree),使每个节点node的新值等于原树中大于或等于node->val的值之和。
二叉搜索树应满足下列约束条件：

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

输入输出样例

avatar

Input: [4,1,6,0,2,5,7,null,null,null,3,null,null,null,8]
Output: [30,36,21,36,35,26,15,null,null,null,33,null,null,null,8]

题解

通常对于二叉树的题目，我们首先需要思考的是，它的每个节点应该做什么。但是对于这道题目可能不是很适用。
在仔细的审题一下，BST的每个节点左小右大。这似乎是一个有效的条件，既然累加和是计算大于等于当前值的所有元素之和，那么每个节点都去计算右子树的和，不就可以了吗？
这是不可以的，因为这对于一个节点来说，确实右子树都是比它在的元素，但是问题是它的父节点也可能是比它大的元素呀。这个没法确定，我们没有直接触及父节点的指针，所以二叉树的通用思路在这里用不了。
对于这道题目，我们可以使用BST的性质——BST的中序遍历后，元素顺序是升序来进行解题。对于这道题目，我们还需要有所改变。我们应先从右子树开始进行一个降序遍历，因此，我们将right与left的递归先后顺序调换一下就可以了。具体代码如下所示：

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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int sum = 0;
    TreeNode* convertBST(TreeNode* root) {
        inorder(root);
        return root;
    }
    void inorder(TreeNode* root) {
        if (root == nullptr) return;
        inorder(root->right);
        sum += root->val;
        root->val = sum;
        inorder(root->left);
    }
};