Java 求解如何把二叉搜索树转换为累加树

一、题目

给出二叉搜索树的根节点，该树的节点值各不相同，请你将其转换为累加树（Greater Sum Tree），使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。

提醒一下，二叉搜索树满足下列约束条件：
节点的左子树仅包含键 小于 节点键的节点。
节点的右子树仅包含键 大于 节点键的节点。
左右子树也必须是二叉搜索树。

二、题解

观察示例图发现，树的遍历顺序为右，中，左的顺序，每个节点的值，是按照这个顺序累加的状态

由于是需要累加，所以需要pre指针记录当前遍历节点cur的前一个节点，方便累加

（1）确定递归函数及返回值

题目需要遍历整棵树，同时需要定义一个全局变量 pre，用来保存 cur节点的前一个节点的数值

（2）确定递归终止条件

遇到空就终止

（3）确定单层递归的逻辑

遍历的顺序，右，中，左

三、代码

class Solution {
    // 记录前驱节点
    int pre = 0;

    public TreeNode convertBST(TreeNode root) {
        // 空节点终止
        if (root == null) {
            return root;
        }
        // 遍历顺序：右，中，左
        convertBST(root.right);
        root.val += pre;
        pre = root.val;
        convertBST(root.left);
        return root;
    }
}

四、总结

观察示例节点的规律，需要记录上个节点的情况，注意引入前驱节点pre

到此这篇关于Java 求解如何把二叉搜索树转换为累加树的文章就介绍到这了,更多相关Java 二叉搜索树转换为累加树内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

赞 (0)

相关推荐

  • Java基础之二叉搜索树的基本操作

    Java基础之二叉搜索树的基本操作

    一.二叉搜索树插入元素 /** * user:ypc: * date:2021-05-18; * time: 15:09; */ class Node { int val; Node left; Node right; Node(int val) { this.val = val; } } public void insert(int key) { Node node = new Node(key); if (this.root == null) { root = node; } Node cu

  • Java底层基于二叉搜索树实现集合和映射/集合Set功能详解

    本文实例讲述了Java底层基于二叉搜索树实现集合和映射功能.分享给大家供大家参考,具体如下: 前言:在第5章的系列学习中,已经实现了关于二叉搜索树的相关操作,详情查看第5章即可.在本节中着重学习使用底层是我们已经封装好的二叉搜索树相关操作来实现一个基本的集合(set)这种数据结构. 集合set的特性: 集合Set存储的元素是无序的.不可重复的.为了能达到这种特性就需要寻找可以作为支撑的底层数据结构. 这里选用之前自己实现的二叉搜索树,这是由于该二叉树是不能盛放重复元素的.因此我们可以使用二叉搜索

  • Java删除二叉搜索树的任意元素的方法详解

    本文实例讲述了Java删除二叉搜索树的任意元素的方法.分享给大家供大家参考,具体如下: 一.删除思路分析 在删除二叉搜索树的任意元素时,会有三种情况: 1.1 删除只有左孩子的节点 节点删除之后,将左孩子所在的二叉树取代其位置:连在原来节点父亲元素右节点的位置,比如在图中需要删除58这个节点. 删除58这个节点后,如下图所示: 1.2 删除只有右孩子的节点: 节点删除之后,将右孩子所在的二叉树取代其位置:连在原来节点的位置,比如在下图中需要删除58这个节点. 删除58这个节点后,如下图所示: 这

  • 利用java实现二叉搜索树

    利用java实现二叉搜索树

    二叉搜索树的定义 它是一颗二叉树 任一节点的左子树上的所有节点的值一定小于该节点的值 任一节点的右子树上的所有节点的值一定大于该节点的值 特点: 二叉搜索树的中序遍历结果是有序的(升序)! 实现一颗二叉搜索树 实现二叉搜索树,将实现插入,删除,查找三个方面 二叉搜索树的节点是不可以进行修改的,如果修改,则可能会导致搜索树的错误 二叉搜索树的定义类 二叉搜索树的节点类 -- class Node 二叉搜索树的属性:要找到一颗二叉搜索树只需要知道这颗树的根节点. public class BST {

  • Java 求解如何把二叉搜索树转换为累加树

    Java 求解如何把二叉搜索树转换为累加树

    一.题目 给出二叉搜索树的根节点,该树的节点值各不相同,请你将其转换为累加树(Greater Sum Tree),使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和. 提醒一下,二叉搜索树满足下列约束条件: 节点的左子树仅包含键 小于 节点键的节点. 节点的右子树仅包含键 大于 节点键的节点. 左右子树也必须是二叉搜索树. 二.题解 观察示例图发现,树的遍历顺序为右,中,左的顺序,每个节点的值,是按照这个顺序累加的状态 由于是需要累加,所以需要pre指针记录当前遍历节点

  • Java动态规划方式解决不同的二叉搜索树

    Java动态规划方式解决不同的二叉搜索树

    目录 一.题目描述 二.思路 三.代码 一.题目描述 给你一个整数 n ,求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种?返回满足题意的二叉搜索树的种数. 来源:https://leetcode.cn/problems/unique-binary-search-trees/ 二.思路 本题可以使用动态规划的方式解决,我们先来看一下大题思路.以 n = 3 为例,n = 3 时的不同的二叉搜索树数目,可以通过分别 以 1 为根节点,以 2 为根节点,以 3 为根节点

  • Java C++ 算法题解leetcode669修剪二叉搜索树示例

    Java C++ 算法题解leetcode669修剪二叉搜索树示例

    目录 题目要求 思路一:模拟迭代 Java C++ 思路二:递归 Java C++ Rust 题目要求 思路一:模拟迭代 依次判断每个节点是否合法: 首先找出结果的根,若原根小了就拉右边的过来,大了拉左边的过来做新根: 然后分别判断左右子树的大小,由于二叉搜索树的性质,子树只需要判断一边就好: 左子树判断是否>low,合法就向左下走,不合法往右下: 右子树判断是否<high,合法就向右下走,不合法往左下. Java class Solution { public TreeNode trimBS

  • Java 实现二叉搜索树的查找、插入、删除、遍历

    Java 实现二叉搜索树的查找、插入、删除、遍历

    由于最近想要阅读下JDK1.8 中HashMap的具体实现,但是由于HashMap的实现中用到了红黑树,所以我觉得有必要先复习下红黑树的相关知识,所以写下这篇随笔备忘,有不对的地方请指出- 学习红黑树,我觉得有必要从二叉搜索树开始学起,本篇随笔就主要介绍Java实现二叉搜索树的查找.插入.删除.遍历等内容. 二叉搜索树需满足以下四个条件: 若任意节点的左子树不空,则左子树上所有结点的值均小于它的根结点的值: 若任意节点的右子树不空,则右子树上所有结点的值均大于它的根结点的值: 任意节点的左.右子

  • Java创建二叉搜索树,实现搜索,插入,删除的操作实例

    Java实现的二叉搜索树,并实现对该树的搜索,插入,删除操作(合并删除,复制删除) 首先我们要有一个编码的思路,大致如下: 1.查找:根据二叉搜索树的数据特点,我们可以根据节点的值得比较来实现查找,查找值大于当前节点时向右走,反之向左走! 2.插入:我们应该知道,插入的全部都是叶子节点,所以我们就需要找到要进行插入的叶子节点的位置,插入的思路与查找的思路一致. 3.删除: 1)合并删除:一般来说会遇到以下几种情况,被删节点有左子树没右子树,此时要让当前节点的父节点指向当前节点的左子树:当被删节点

  • java实现 二叉搜索树功能

    一.概念 二叉搜索树也成二叉排序树,它有这么一个特点,某个节点,若其有两个子节点,则一定满足,左子节点值一定小于该节点值,右子节点值一定大于该节点值,对于非基本类型的比较,可以实现Comparator接口,在本文中为了方便,采用了int类型数据进行操作. 要想实现一颗二叉树,肯定得从它的增加说起,只有把树构建出来了,才能使用其他操作. 二.二叉搜索树构建 谈起二叉树的增加,肯定先得构建一个表示节点的类,该节点的类,有这么几个属性,节点的值,节点的父节点.左节点.右节点这四个属性,代码如下 sta

  • Java二叉搜索树遍历操作详解【前序、中序、后序、层次、广度优先遍历】

    本文实例讲述了Java二叉搜索树遍历操作.分享给大家供大家参考,具体如下: 前言:在上一节Java二叉搜索树基础中,我们对树及其相关知识做了了解,对二叉搜索树做了基本的实现,下面我们继续完善我们的二叉搜索树. 对于二叉树,有深度遍历和广度遍历,深度遍历有前序.中序以及后序三种遍历方法,广度遍历即我们寻常所说的层次遍历,如图: 因为树的定义本身就是递归定义,所以对于前序.中序以及后序这三种遍历我们使用递归的方法实现,而对于广度优先遍历需要选择其他数据结构实现,本例中我们使用队列来实现广度优先遍历.

  • Java二叉搜索树基础原理与实现方法详解

    本文实例讲述了Java二叉搜索树基础原理与实现方法.分享给大家供大家参考,具体如下: 前言:本文通过先通过了解一些二叉树基础知识,然后在转向学习二分搜索树. 1 树 1.1 树的定义 树(Tree)是n(n>=0)个节点的有限集.n=0时称为空树.在任意一颗非空树中: (1)有且仅有一个特定的称为根(Root)的节点: (2)当n>1时,其余节点可分为m(m>0)个互不相交的有限集T1.T2........Tn,其中每一个集合本身又是一棵树,并且称为根的子树. 此外,树的定义还需要强调以

随机推荐