专栏首页眯眯眼猫头鹰的小树杈leetcode538. Convert BST to Greater Tree

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

现有一棵二叉搜索树,需要将二叉搜索树上每个节点的值转化为大于等于该节点值的所有值的和。

思路和代码

这一题可以通过递归的思路来计算出每个节点的目标值。可以知道,每一个节点大于当前节点的值寄存于距离自己最近的左节点以及自己的右节点中。因此计算每个节点时,需要传入当前节点以及距离自己最近的左父节点。

public TreeNode convertBST(TreeNode root) {  
    if (root == null) {  
        return null;  
    }  
    return convertBST(root, null);  
}  
  
public TreeNode convertBST(TreeNode cur, TreeNode leftParent) {  
    TreeNode newCur = new TreeNode(cur.val);  
    if (leftParent != null) {  
        newCur.val += leftParent.val;  
    }  
    if (cur.right != null) {  
        newCur.right = convertBST(cur.right, leftParent);  
        cur.val += cur.right.val;  
        newCur.val += cur.right.val;  
    }  
    if (cur.left != null) {  
        TreeNode newLeft = convertBST(cur.left, newCur);  
        cur.val += cur.left.val;  
        newCur.left = newLeft;  
    }  
    return newCur;  
}

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 猫头鹰的深夜翻译:JDK Vs. JRE Vs. JVM之间的区别

    JDK通常用来开发Java应用和插件。基本上可以认为是一个软件开发环境。JDK包含Java Runtime Environment(JRE),JRE包含加载器/...

    眯眯眼的猫头鹰
  • leetcode331. Verify Preorder Serialization of a Binary Tree

    我们知道,任何两个节点都可以和位于左边的非叶节点构成一棵有三个节点的树。如果我们从右往左看先序遍历,就知道后两个节点如果遇到第三个节点,则该节点就应当是这两个节...

    眯眯眼的猫头鹰
  • 猫头鹰的深夜翻译:开发者必须了解的分支发布模型

    想要深入了解Git和中心化代码版本管理系统的优缺点比较,可以在网上自行查询,这个话题一直争论不休。作为一个开发者,我更倾向于使用Git。Git确实改变了开发者对...

    眯眯眼的猫头鹰
  • 每日一题 剑指offer(二叉树中和为某一值的路径)

    编程是很多偏计算机、人工智能领域必须掌握的一项技能,此编程能力在学习和工作中起着重要的作用。因此小白决定开辟一个新的板块“每日一题”,通过每天一道编程题目来强化...

    小白学视觉
  • WPF 多线程 UI:设计一个异步加载 UI 的容器

    2018-09-08 12:53

    walterlv
  • 【程序源代码】I桌面版聊天程序

    程序源代码
  • Gartner整理的未来5年流行技术词

    Digitalization is boundless, A dozen other emerging technology trends are destin...

    黑光技术
  • BERT-hLSTMS:面向视觉叙事的BERT和层次化LSTM(CS CL)

    面向视觉叙事是一项富有创意和挑战性的任务,旨在自动生成一系列图像的一个故事式描述。以往面向视觉叙事方法生成的描述缺乏一致性,因为它们使用字级序列生成方法,并且没...

    谭雪儿
  • 使用移动环境传感器的智能手机健康评估(CS CY)

    心理健康和整体健康是社会日益关注的问题。环境因素会导致精神疾病,并有能力影响一个人的健康。这项研究提出了一个基于智能手机的健康评估系统,并检查了个人环境和健康是...

    用户7495559
  • Web安全漏洞之CSRF

    在了解 CSRF 之前我们需要科普两个前提。首先是登录权限验证的方式有很多种,目前绝大多数网站采用的还是 session 会话任务的方式。session 机制简...

    lyb-geek

扫码关注云+社区

领取腾讯云代金券