把二叉搜索树转换为累加树

简介: 把二叉搜索树转换为累加树

538. 把二叉搜索树转换为累加树

一、题目描述:

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

提醒一下,二叉搜索树满足下列约束条件:

节点的左子树仅包含键 小于 节点键的节点。
节点的右子树仅包含键 大于 节点键的节点。
左右子树也必须是二叉搜索树。
注意:本题和 1038: https://leetcode-cn.com/problems/binary-search-tree-to-greater-sum-tree/ 相同

示例 1:

输入:[4,1,6,0,2,5,7,null,null,null,3,null,null,null,8]
输出:[30,36,21,36,35,26,15,null,null,null,33,null,null,null,8]
示例 2:

输入:root = [0,null,1]
输出:[1,null,1]
示例 3:

输入:root = [1,0,2]
输出:[3,3,2]
示例 4:

输入:root = [3,2,4,1]
输出:[7,9,4,10]

提示:

树中的节点数介于 0 和 104 之间。
每个节点的值介于 -104 和 104 之间。
树中的所有值 互不相同 。
给定的树为二叉搜索树。

来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/convert-bst-to-greater-tree
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

二、思路分析:

二叉搜索树满足下列约束条件:

节点的左子树仅包含键 小于 节点键的节点。
节点的右子树仅包含键 大于 节点键的节点。
左右子树也必须是二叉搜索树。
题目意思是先更新右子树值,再更新自己的值,再更新左子树的值
不难想到树的中序遍历 -> 左根右
但是可以看到这与题目需要的右根左正好相反,那么我们就按题目给定要求,调整一下中序遍历遍历的顺序,将其反向,反向中序遍历

三、AC 代码:

class Solution {
    int sum = 0;

    public TreeNode convertBST(TreeNode root) {
        if (root != null) {
            convertBST(root.right);
            sum += root.val;
            root.val = sum;
            convertBST(root.left);
        }
        return root;
    }
}

四、总结:

image.png

掘友们,解题不易,留下个赞或评论再走吧!谢啦~ 💐

希望对你有帮助

期待下次再见~

相关文章
【数据结构】单值二叉树 & 相同的树 & 翻转二叉树(五)
【数据结构】单值二叉树 & 相同的树 & 翻转二叉树(五)
49 0
|
6月前
|
存储 算法 程序员
【数据结构-二叉树 八】【遍历求和】:求根到叶子节点数字之和
【数据结构-二叉树 八】【遍历求和】:求根到叶子节点数字之和
85 0
|
6月前
|
Java C++ Python
leetcode-538:把二叉搜索树转换为累加树
leetcode-538:把二叉搜索树转换为累加树
36 0
33_把二叉搜索树转换为累加树
33_把二叉搜索树转换为累加树
32_将有序数组转换为平衡二叉搜索树
32_将有序数组转换为平衡二叉搜索树
|
1月前
二叉树的深度、路径总和、将有序数组转换为二叉搜索树、二叉搜索树迭代器(2022/02/23)
二叉树的深度、路径总和、将有序数组转换为二叉搜索树、二叉搜索树迭代器(2022/02/23)
12 0
|
5月前
|
算法
数据结构和算法学习记录——层序遍历(层次遍历)、二叉树遍历的应用(输出二叉树中的叶节点、求二叉树的高度、二元运算表达式树及其遍历、由两种遍历序列确定二叉树)
数据结构和算法学习记录——层序遍历(层次遍历)、二叉树遍历的应用(输出二叉树中的叶节点、求二叉树的高度、二元运算表达式树及其遍历、由两种遍历序列确定二叉树)
48 0
算法训练Day23|669. 修剪二叉搜索树 ● 108.将有序数组转换为二叉搜索树 ● 538.把二叉搜索树转换为累加树
算法训练Day23|669. 修剪二叉搜索树 ● 108.将有序数组转换为二叉搜索树 ● 538.把二叉搜索树转换为累加树
二叉树习题系列1--将二叉搜索树排序树转化为双向链表
二叉树习题系列1--将二叉搜索树排序树转化为双向链表
|
算法 Java
代码随想录训练营day23| 669. 修剪二叉搜索树 108.将有序数组转换为二叉搜索树 538.把二叉搜索树转换为累加树...
代码随想录训练营day23| 669. 修剪二叉搜索树 108.将有序数组转换为二叉搜索树 538.把二叉搜索树转换为累加树...