538.把二叉搜索树转换为累加树
1、概要
给出二叉 搜索 树的根节点，该树的节点值各不相同，请你将其转换为累加树（Greater Sum Tree），使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。
提醒一下，二叉搜索树满足下列约束条件：
节点的左子树仅包含键 小于 节点键的节点。 节点的右子树仅包含键 大于 节点键的节点。 左右子树也必须是二叉搜索树。
累加树是一种对二叉搜索树进行转换得到的特殊树形数据结构。在二叉搜索树中，节点的左子树只包含键值小于节点键值的节点，右子树只包含键值大于节点键值的节点，而左右子树自身也是二叉搜索树。
在累加树中，每个节点的值变为原二叉搜索树中所有大于或等于该节点值的节点之和。这个过程中，需要遍历整个二叉搜索树，计算每个节点的子树中所有大于或等于该节点值的节点之和，然后将这个和加到该节点的值上。
换一个角度来看，这就是一个有序数组[2, 5, 13]，求从后到前的累加数组，是不是感觉这就简单了。
从树中可以看出累加的顺序是右中左，所以我们需要反中序遍历这个二叉树，然后顺序累加就可以了。
2、思路
递归
本题依然需要一个pre指针记录当前遍历节点cur的前一个节点，这样才方便做累加。
- 确认递归函数参数以及返回值
int sum;
public void convertBST1(TreeNode root) {
- 确定终止条件
if (root == null) {
return;
}
- 确定单层递归逻辑
要右中左来遍历二叉树， 中节点的处理逻辑就是让cur的数值加上前一个节点的数值。
convertBST1(root.right);
sum += root.val;
root.val = sum;
convertBST1(root.left);
迭代
迭代法其实就是中序模板题了，用栈，顺序左中右。反过来即是右中左。在操作处执行单层逻辑。累加，记录指针赋新值。
3、代码
class Solution {
int sum;
public TreeNode convertBST(TreeNode root) {
sum = 0;
// return reCurSion(root);
return iteRaTion(root);
}
public TreeNode reCurSion(TreeNode root){
if(root == null){
return null;
}
reCurSion(root.right);
root.val += sum;
sum = root.val;
reCurSion(root.left);
return root;
}
public TreeNode iteRaTion(TreeNode root){
Stack<TreeNode> stack = new Stack<>();
if(root == null){
return null;
}
stack.add(root);
while(!stack.isEmpty()){
TreeNode cur = stack.pop();
if(cur != null){
if(cur.left!=null){
stack.add(cur.left);
}
stack.add(cur);
stack.add(null);
if(cur.right!=null){
stack.add(cur.right);
}
}else{
TreeNode temp = stack.pop();
temp.val +=sum;
sum = temp.val;
}
}
return root;
}
}