LeetCode算法题-Convert BST to Greater Tree（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<TreeNode> stack = new Stack<TreeNode>();    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+篇，公众号对话框回复【数据结构与算法】、【算法】、【数据结构】中的任一关键词，获取系列文章合集。

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