这是悦乐书的第 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 + 篇, 公众号对话框回复[数据结构与算法] ,[算法] ,[数据结构] 中的任一关键词, 获取系列文章合集.
以上就是全部内容, 如果大家有什么好的解法思路, 建议或者其他问题, 可以下方留言交流, 点赞, 留言, 转发就是对我最大的回报和支持!
来源: http://www.jianshu.com/p/4d7fa58c05f3