/**
Given the root of a Binary Search Tree (BST), convert it to a Greater Tree such
that every key of the original BST is changed to the original key plus the sum
of all keys greater than the original key in BST.
As a reminder, a binary search tree is a tree that satisfies these constraints:
The left subtree of a node contains only nodes with keys less than the node's
key.
The right subtree of a node contains only nodes with keys greater than the
node's key.
Both the left and right subtrees must also be binary search trees.
Example 1:
Input: root = [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]
Example 2:
Input: root = [0,null,1]
Output: [1,null,1]
Constraints:
The number of nodes in the tree is in the range [0, 10⁴].
-10⁴ <= Node.val <= 10⁴
All the values in the tree are unique.
root is guaranteed to be a valid binary search tree.
Note: This question is the same as 1038: https://leetcode.com/problems/binary-
search-tree-to-greater-sum-tree/
Related Topics树 | 深度优先搜索 | 二叉搜索树 | 二叉树
👍 800, 👎 0
*/
//leetcode submit region begin(Prohibit modification and deletion)
/**
* Definition for a binary tree node.
* 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;
* }
* }
*/
class Solution {
public TreeNode convertBST(TreeNode root) {
if (root == null) {
return root;
}
Map<TreeNode, Integer> leftSum = new HashMap<>();
Map<TreeNode, Integer> rightSum = new HashMap<>();
getSum(leftSum, rightSum, root);
doPlus(rightSum, root, null);
return root;
}
private void getSum(Map<TreeNode, Integer> leftSum, Map<TreeNode, Integer> rightSum, TreeNode node) {
if (node.left != null) {
getSum(leftSum, rightSum, node.left);
int total = leftSum.get(node.left) + rightSum.get(node.left) + node.left.val;
leftSum.put(node, total);
} else {
leftSum.put(node, 0);
}
if (node.right != null) {
getSum(leftSum, rightSum, node.right);
int total = leftSum.get(node.right) + rightSum.get(node.right) + node.right.val;
rightSum.put(node, total);
} else {
rightSum.put(node, 0);
}
}
private void doPlus(Map<TreeNode, Integer> rightSum, TreeNode node, TreeNode bigFather) {
node.val += rightSum.get(node);
if (bigFather != null) {
node.val += bigFather.val;
}
if (node.left != null) {
doPlus(rightSum, node.left, node);
}
if (node.right != null) {
doPlus(rightSum, node.right, bigFather);
}
}
}
//leetcode submit region end(Prohibit modification and deletion)
