LeetCode算法题ConvertBSTtoGreaterTree（Java实现）

这是悦乐书的第255次更新，第268篇原创

01 看题和准备

今天介绍的是LeetCode算法题中Easy级别的第122题（顺位题号是538）。给定二进制搜索树（BST），将其转换为更大树，使原始BST的每个键都更改为原始键加上所有键的总和大于BST中的原始键。例如：

输入：二进制搜索树的根，如下所示：

5
/ \
2 13

输出：大树的根，如下所示：

18
/ \
20 13

本次解题使用的开发工具是eclipse，jdk使用的版本是1.8，环境是win7 64位系统，使用Java语言编写和测试。

02 第一种解法

题目的意思是将一个二叉搜索树的节点按照右根左的顺序累加，用不断累加的值作为原节点新的节点值，至于返回后新的二叉树，题目并没有要求是二叉搜索树，因此我们可以直接使用递归方法，顺序为右根左，另外还需要定义一个全局变量sum，来依次累加节点值。

此解法的时间复杂度是O(n)，空间复杂度是O(n)。

private int sum = 0;
public TreeNode convertBST(TreeNode root) {
if (root == null) {
return null;
}
convertBST(root.right);
sum += root.val;
root.val = sum;
convertBST(root.left);
return root;
}

03 第二种解法

我们还可以使用迭代的方法来解，借助栈（或者队列）来实现。先将当前节点的所有右子节点进栈，然后出栈一个节点，此节点是最下面一层的第一个右子节点，然后节点值开始累加，然后再将左子节点依次进栈。

此解法的时间复杂度是O(n)，空间复杂度是O(n)。

public TreeNode convertBST2(TreeNode root) {
if (root == null) {
return null;
}
int sum = 0;
Stack stack = new Stack();
TreeNode node = root;
while (!stack.isEmpty() || node != null) {
while (node != null) {
stack.push(node);
node = node.right;
}
node = stack.pop();
sum += node.val;
node.val = sum;
node = node.left;
}
return root;
}

04 第三种解法

还有一种比较厉害的解法，Reverse Morris In-order Traversal（逆向莫里斯有序遍历），是由一个叫Morris的人提出的，感兴趣的可以去仔细研究下。

此解法的时间复杂度是O(n)，空间复杂度是O(1)。

public TreeNode convertBST3(TreeNode root) {
TreeNode cur = root;
int sum = 0;
while (cur != null) {
if (cur.right == null) {
sum += cur.val;
cur.val = sum;
cur = cur.left;
} else {
TreeNode prev = cur.right;
while (prev.left != null && prev.left != cur) {
prev = prev.left;
}
if (prev.left == null) {
prev.left = cur;
cur = cur.right;
} else {
prev.left = null;
sum += cur.val;
cur.val = sum;
cur = cur.left;
}
}
}
return root;
}

05 小结

算法专题目前已日更超过三个月，算法题文章122+篇，公众号对话框回复【数据结构与算法】、【算法】、【数据结构】中的任一关键词，获取系列文章合集。

以上就是全部内容，如果大家有什么好的解法思路、建议或者其他问题，可以下方留言交流，点赞、留言、转发就是对我最大的回报和支持！