【Leetcode刷题篇】leetcode538 把二叉搜索树转换为累加树
发布日期:2021-06-29 15:35:20
浏览次数:4
分类:技术文章
本文共 868 字,大约阅读时间需要 2 分钟。
给出二叉 搜索 树的根节点,该树的节点值各不相同,请你将其转换为累加树(Greater Sum Tree),使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。
提醒一下,二叉搜索树满足下列约束条件:
节点的左子树仅包含键 小于 节点键的节点。 节点的右子树仅包含键 大于 节点键的节点。 左右子树也必须是二叉搜索树。
解题思路:
前序遍历:根左右 中序遍历:左根右 后序遍历:左右根
因此,而本遍历顺序为右根左。
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */class Solution { 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; } }
转载地址:https://codingchaozhang.blog.csdn.net/article/details/111348005 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
不错!
[***.144.177.141]2024年04月22日 16时02分33秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
面向对象之4:(package关键字)包,(import关键字)导入,的总结:
2019-04-29
面向对象之5:面向对象三大特性之 继承 、super关键字 的总结:
2019-04-29
面向对象之7:面向对象三大特性之 多态、instanceof关键字(运算符)的总结:
2019-04-29
面向对象之9:抽象类、final关键字、(JDK1.8之后) 接口 的总结:
2019-04-29
面向对象之10: 静态内部类、实例内部类、局部内部类 、匿名内部类 的总结
2019-04-29
面向对象之11:枚举类 及 使用细节 总结:
2019-04-29
面试题:如何将任意一个 一维数组 转换成任意的 二维数组
2019-04-29
面向对象之15:开发中的常用类之二:Date、Time、Timestamp、Calendar、LocalDate、LocalTime、LocalDateTime、……的使用总结:
2019-04-29
面向对象之16:一文 彻底搞懂Java中的泛型、泛型的 使用细节 及 注意事项:
2019-04-29
手写 System.arraycopy API 的 数组扩容、数组拷贝 的功能。
2019-04-29
替换国内conda和pip的默认下载源
2019-04-29