leetcode538 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 简单来说,就是把一棵BST的所有节点的值转化为其本身加上所有比它的节点的和。

解题思路

当看到这个题目的时候,我是懵逼的。很明显存在重复计算和,所以我一开始想的是动态规划,然后我花了一个图。

红色代表节点应该被访问的顺序,定睛一看,这似乎和中序遍历差不多啊。只不过中序遍历是左中右,而这里是右中左而已。 为了追求效率,采取非递归的遍历,设置一个值保存之前的和。

public class leetcode538 {
    public TreeNode convertBST(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        TreeNode p = root;
        int res = 0;
        while (!stack.isEmpty()||p!=null){
            if(p!=null) {
                stack.push(p);
                p = p.right;
            }
            else {
                p = stack.pop();
                int temp = p.val;
                p.val += res;
                res += temp;
                p = p.left;
            }
        }
        return root;
    }
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏和蔼的张星的图像处理专栏

85. 在二叉查找树中插入节点常规操作

You can assume there is no duplicate values in this tree + node.

1512
来自专栏猿人谷

单链表反转的分析及实现

我先画一个单链表,这个单链表有4个元素。我的思路就是,每次把第二个元素提到最前面来。比如下面是第一次交换,我们先让头结点的next域指向结点a2,再让结点a1...

94710
来自专栏Phoenix的Android之旅

Java 集合 Vector

List有三种实现,ArrayList, LinkedList, Vector, 它们的区别在于, ArrayList是非线程安全的, Vector则是线程安全...

722
来自专栏日常分享

通过BitSet完成对单词使用字母的统计

  BitSet类实现了一组位或标记(flag),这些位可被分别设置或清除。当需要跟踪一组布尔值时,这种类很有用。

862
来自专栏算法与数据结构

数据结构 链表(循环)

#include<stdio.h> #include<malloc.h> #include<stdlib.h> //函数状态码定义 #define TRUE ...

1977
来自专栏数据结构与算法

24:打印月历

24:打印月历 查看 提交 统计 提问 总时间限制: 1000ms 内存限制: 65536kB描述 给定年月,打印当月的月历表。 输入输入为一行两个整数,...

3446
来自专栏Bingo的深度学习杂货店

Q112 Path Sum

Given a binary tree and a sum, determine if the tree has a root-to-leaf path suc...

3397
来自专栏Java3y

二叉树就这么简单

一、二叉树就是这么简单 本文撇开一些非常苦涩、难以理解的概念来讲讲二叉树,仅入门观看(或复习)…. 首先,我们来讲讲什么是树: 树是一种非线性的数据结构,相对于...

4868
来自专栏null的专栏

挑战数据结构和算法面试题——二叉搜索树的后序遍历

题目来源“数据结构与算法面试题80道”。在此给出我的解法,如你有更好的解法,欢迎留言。 ? 分析: 根据二叉查找树的定义,二叉查找树或者是一棵空二叉树,或者是...

3544
来自专栏老马说编程

(32) 剖析日期和时间 / 计算机程序的思维逻辑

本节和下节,我们讨论在Java中如何进行日期和时间相关的操作。 日期和时间是一个比较复杂的概念,Java API中对它的支持不是特别好,有一个第三方的类库反而特...

20110

扫码关注云+社区