538 Convert BST to Greater Tree 把二叉搜索树转换为累加树
Description:
Given 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 sum of all keys greater than the original key in BST.
Example:
Input: The root of a Binary Search Tree like this:
5
/ \
2 13
Output: The root of a Greater Tree like this:
18
/ \
20 13
题目描述:
给定一个二叉搜索树（Binary Search Tree），把它转换成为累加树（Greater Tree)，使得每个节点的值是原来的节点值加上所有大于它的节点值之和。
示例 :
例如：
输入: 二叉搜索树:
5
/ \
2 13
输出: 转换为累加树:
18
/ \
20 13
思路:
- 先计算所有数字之和, 然后按照先序遍历给各个结点赋值
- 按照右 -> 根 -> 左的顺序记录结点的值并累加
可以用递归和迭代解决
时间复杂度O(n), 空间复杂度O(n)
代码:
C++:
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution
{
public:
TreeNode* convertBST(TreeNode* root)
{
int pre = 0;
order(root, pre);
return root;
}
private:
void order(TreeNode* root, int &pre)
{
if (!root) return;
stack<TreeNode*> s;
while (root or s.size())
{
if (root)
{
s.push(root);
root = root -> right;
}
else
{
root = s.top();
s.pop();
root -> val += pre;
pre = root -> val;
root = root -> left;
}
}
}
};
Java:
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
private int pre = 0;
public TreeNode convertBST(TreeNode root) {
order(root);
return root;
}
private void order(TreeNode root) {
if (root == null) return;
order(root.right);
root.val += pre;
pre = root.val;
order(root.left);
}
}
Python:
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def convertBST(self, root: TreeNode) -> TreeNode:
s, l, p, pre = 0, [], root, 0
def dfs(root: TreeNode) -> int:
if not root:
return 0
return root.val + dfs(root.left) + dfs(root.right)
s = dfs(root)
while p or l:
if p:
l.append(p)
p = p.left
else:
p = l.pop()
pre = p.val
p.val = s
s -= pre
p = p.right
return root
