深度优先遍历 DFS
解题思路
题意是 每个节点 node 的新值等于 原树中大于或等于 node.val 的值之和 ，那就是要找到大于等于当前节点的所有值进行累加；
由于搜索二叉树的中序遍历是一个 单调递增序列 ，可以根据这个 单调递增序列 来求出累加树，是从后向前累加的；
则可以利用 反中序遍历 右->根->左 递归求出每个 node 的累加值；
复杂度
-
时间复杂度：
O(n)，其中 n 为二叉搜索树的节点个数； -
空间复杂度：
O(n)，最坏情况下，二叉搜索树退化成一条链，因此递归需要O(n)的栈空间；
代码实现
var convertBST = function (root) {
const dfs = (root) => {
if (root === null) return;
dfs(root.right);
sum += root.val;
root.val = sum;
dfs(root.left);
};
let sum = 0;
dfs(root);
return root;
};
广度优先遍历 BFS
解题思路
利用迭代进行 反中序遍历 右->根->左；
在遍历的过程中不断求出每个节点的 前缀和；
复杂度
-
时间复杂度：
O(n)，其中 n 为二叉搜索树的节点个数； -
空间复杂度：
O(1)；
代码实现
var convertBST = function (root) {
const res = [];
const stk = [];
let sum = 0;
let dmg = root;
while (root || stk.length > 0) {
// 1. 一直向右查找，找到最右边的节点
while (root) {
stk.push(root);
root = root.right;
}
// 2. 出栈栈顶节点
root = stk.pop();
sum += root.val;
root.val = sum;
res.push(root.val);
// 3. 利用栈顶节点，去寻找左孩子节点
root = root.left;
}
return dmg;
};
打赏作者
您的打赏是我前进的动力
微信
支付宝
leetcode🧑💻 15. 三数之和
上一篇
评论
