链接
https://leetcode-cn.com/problems/convert-bst-to-greater-tree/
耗时
解题:10 min
题解:14 min
题意
给定一个二叉搜索树(Binary Search Tree),把它转换成为累加树(Greater Sum Tree),使得每个节点的值是原来的节点值加上所有大于它的节点值之和。
注意: 本题和 1038. 从二叉搜索树到更大和树 相同,代码只需需改函数名即可 AC 😃
思路
根据二叉搜索树的性质,当前节点有且只有它的右子树上的所有节点大于当前节点值。所以按 dfs 右节点、本身、左节点的顺序,找到最大值,第二大的值,以此类推,然后一个一个往上累加,更新每个节点的值为 本身加累加值。
时间复杂度:
O
(
n
)
O(n)
O(n)
AC代码
class Solution {
public:
int sum = 0;
TreeNode* convertBST(TreeNode* root) {
if(root == NULL) return NULL;
convertBST(root->right);
root->val += sum;
sum = root->val;
convertBST(root->left);
return root;
}
};
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)