LeetCode算法题-Convert BST to Greater Tree（Java实现）

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

01 看题和准备

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

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

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

本次解题使用的开发工具是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+篇，公众号对话框回复【数据结构与算法】、【算法】、【数据结构】中的任一关键词，获取系列文章合集。

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

巴特西