题干描述
力扣入口
给出二叉搜索树的根节点,该树的节点值各不相同,请你将其转换为累加树(Greater Sum Tree),使每个节点 node的新值等于原树中大于或等于node.val的值之和。
提醒一下,二叉搜索树满足下列约束条件:
节点的左子树仅包含键 小于 节点键的节点。 节点的右子树仅包含键 大于 节点键的节点。 左右子树也必须是二叉搜索树。
示例 1:
- 输入:[4,1,6,0,2,5,7,null,null,null,3,null,null,null,8]
- 输出:[30,36,21,36,35,26,15,null,null,null,33,null,null,null,8]
示例 2:
- 输入:root = [0,null,1]
- 输出:[1,null,1]
示例 3:
- 输入:root = [1,0,2]
- 输出:[3,3,2]
示例 4:
- 输入:root = [3,2,4,1]
- 输出:[7,9,4,10]
提示:
- 树中的节点数介于 0 和 104 之间。
- 每个节点的值介于 -104 和 104 之间。
- 树中的所有值互不相同。
- 给定的树为二叉搜索树。
解题思路
利用二叉搜素树的有序性。
其实这就是一棵树,大家可能看起来有点别扭,换一个角度来看,这就是一个有序数组[2, 5, 13],求从后到前的累加数组,也就是[20, 18, 13],是不是感觉这就简单了。
知道如何遍历这个二叉树,也就迎刃而解了,从树中可以看出累加的顺序是右中左,所以我们需要反中序遍历这个二叉树,然后顺序累加就可以了。
递归
遍历顺序如图所示:
本题依然需要一个pre指针记录当前遍历节点cur的前一个节点,这样才方便做累加。
pre指针的使用技巧,我们在二叉树:搜索树的最小绝对差和二叉树:我的众数是多少?都提到了,这是常用的操作手段。
1. 递归函数参数以及返回值
这里很明确了,不需要递归函数的返回值做什么操作了,要遍历整棵树。
同时需要定义一个全局变量pre,用来保存cur节点的前一个节点的数值,定义为int型就可以了。
2. 确定终止条件
遇空就终止。
if(cur == NULL) return;
3. 确定单层递归的逻辑
注意要右中左来遍历二叉树, 中节点的处理逻辑就是让cur的数值加上前一个节点的数值。
迭代
迭代法其实就是中序模板题了,在二叉树:前中后序迭代法和二叉树:前中后序统一方式迭代法 可以选一种自己习惯的写法。
代码实现
递归法
// 538.把二叉搜索树转换为累加树 - 递归
int sum;
public TreeNode convertBST(TreeNode root){
sum = 0;
convertBST1(root);
return root;
}
// 按右中左顺序遍历,累加即可
public void convertBST1(TreeNode root){
if(root == null){
return;
}
convertBST1(root.right);
sum += root.val;
root.val = sum;
convertBST1(root.left);
}
迭代法
// 538.把二叉搜索树转换为累加树 - DFS iteration统一迭代法
public TreeNode convertBST(TreeNode root){
int pre = 0;
Stack<TreeNode> stack = new Stack<>();
if(root == null) // edge case check
return null;
stack.add(root);
while(!stack.isEmpty()){
TreeNode curr = stack.peek();
// curr != null的状况, 只负责存node到check中
if(curr != null){
stack.pop();
if(curr.left != null) // 左
stack.add(curr.left);
stack.add(curr); // 中
stack.add(null);
if(curr.right != null) // 右
stack.add(curr.right);
} else{
stack.pop();
TreeNode temp = stack.pop();
temp.val += pre;
pre = temp.val;
}
}
return root;
}
参考资料:代码随想录-538.把二叉搜索树转换为累加树