把二叉搜索树转换为累加树
难度:
标签:
题目描述
给出二叉 搜索 树的根节点，该树的节点值各不相同，请你将其转换为累加树（Greater Sum Tree），使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。
提醒一下，二叉搜索树满足下列约束条件：
- 节点的左子树仅包含键 小于 节点键的节点。
- 节点的右子树仅包含键 大于 节点键的节点。
- 左右子树也必须是二叉搜索树。
注意：本题和 1038: https://leetcode-cn.com/problems/binary-search-tree-to-greater-sum-tree/ 相同
示例 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之间。 - 树中的所有值 互不相同 。
- 给定的树为二叉搜索树。
代码结果
运行时间: 64 ms, 内存: 17.4 MB
// Java Stream不直接支持树的遍历和操作，这里依然使用递归方式实现。
// 1. 通过反向中序遍历更新每个节点的值。
// 2. 使用lambda表达式和Optional类提高代码简洁性。
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
import java.util.Optional;
public class Solution {
private int sum = 0;
public TreeNode convertBST(TreeNode root) {
Optional.ofNullable(root).ifPresent(node -> {
convertBST(node.right);
sum += node.val;
node.val = sum;
convertBST(node.left);
});
return root;
}
}解释
方法:
这道题的解法使用了反向中序遍历的思路。在二叉搜索树中，中序遍历可以得到一个递增的序列。而本题要求每个节点的新值等于原树中大于等于该节点值的所有节点值之和，实际上就是反向中序遍历累加的过程。具体来说，我们先遍历右子树，然后处理当前节点，最后遍历左子树。在处理当前节点时，我们将当前的累加和加到该节点的值上，然后更新累加和。这样，在遍历完整棵树后，每个节点的值就变成了大于等于该节点的所有节点值之和。
时间复杂度:
O(n)
空间复杂度:
O(n)
代码细节讲解
🦆
为什么选择使用反向中序遍历而不是其他遍历方法来实现累加树？
▷🦆
在反向中序遍历中，加到节点值上的累加和`s`是如何更新的，具体的更新逻辑是什么？
▷🦆
在实际代码实现中，`dfs`函数的终止条件是什么？如何确保不会对空节点进行操作？
▷🦆
在处理完当前节点后，为什么要立即更新累加和`s`，而不是在遍历完左子树或右子树后更新？
▷