友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
538. Convert BST to Greater Tree
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
思路分析
题目要求：原树中大于或等于 node.val 的值之和。二叉搜索树中根遍历是从小到大到，那么反其道而行之，将遍历顺序从“左中右”改为“右中左”，遍历顺序就是从大到小，这样一直累加即可。
一、递归
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int sum = 0;
/**
* 逆向中根遍历
*
* @author D瓜哥 · https://www.diguage.com
* @since 2024-06-26 20:50:34
*/
public TreeNode convertBST(TreeNode root) {
if (null == root) {
return null;
}
convertBST(root.right);
sum += root.val;
root.val = sum;
convertBST(root.left);
return root;
}
二、迭代
基于 Morris 的倒序中根遍历
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
/**
* 基于 Morris 的倒序中根遍历
*
* @author D瓜哥 · https://www.diguage.com
* @since 2024-06-26 20:50:34
*/
public TreeNode convertBST(TreeNode root) {
int sum = 0;
// 反向 Morris
TreeNode cur = root;
TreeNode mostLeft = null;
while (cur != null) {
// 向右转
mostLeft = cur.right;
if (mostLeft != null) {
// 寻找最左边的节点
while (mostLeft.left != null && mostLeft.left != cur) {
mostLeft = mostLeft.left;
}
if (mostLeft.left == null) {
// 第一次访问，将最左节点的左子树指向当前节点
mostLeft.left = cur;
cur = cur.right;
continue;
} else {
// 第二次访问，掐断中间建立的连接
mostLeft.left = null;
}
}
// 计算累加和
sum += cur.val;
cur.val = sum;
cur = cur.left;
}
return root;
}