【Leetcode刷题篇】leetcode538 把二叉搜索树转换为累加树
发布日期:2021-06-29 15:35:20
浏览次数:3
分类:技术文章
本文共 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 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
表示我来过!
[***.240.166.169]2024年04月15日 19时55分40秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
推荐一个优质Linux技术公众号-作者都是一线Linux代码贡献者们哦
2019-04-29
RT-Thread 编程风格指南
2019-04-29
95后高校电子教师,软硬兼修有趣有料!
2019-04-29
使用 STM32 通用 Bootloader ,让 OTA 更加 Easy
2019-04-29
Cache 的基本概念与工作原理
2019-04-29
Android开发技巧!高级Android晋升之View渲染机制,Android篇
2019-04-29
Android程序员必会!Android面试必刷的200道真题,附答案
2019-04-29
Android面试回忆录:掌握这些Android开发热门前沿知识,完整PDF
2019-04-29
Android技术篇!Android面试吃透这一篇就没有拿不到的offer!面试必问
2019-04-29
Android开发快速学习!字节跳动历年校招Android面试真题解析,已拿offer
2019-04-29
Android开发指南!2021中级Android开发面试解答,完整版开放下载
2019-04-29
Android开发指南!带你全面解析Android框架体系架构view篇,已拿offer
2019-04-29