经验首页 前端设计 程序设计 Java相关 移动开发 数据库/运维 软件/图像 大数据/云计算 其他经验
当前位置:技术经验 » 程序设计 » 编程经验 » 查看文章
Leetcode 538. 把二叉搜索树转换为累加树
来源:cnblogs  作者:Gmxbb  时间:2018/9/25 19:12:28  对本文有异议

题目链接

https://leetcode.com/problems/convert-bst-to-greater-tree/description/

题目描述

大于它的节点值之和。

例如:

  1. 输入: 二叉搜索树:
  2. 5
  3. / 2 13
  4. 输出: 转换为累加树:
  5. 18
  6. / 20 13

题解

因为是平衡二叉树,所以有点的节点的值是大于左边的值。可以从右边开始累加,递归遍历即可。

代码

  1. /**
  2. * Definition for a binary tree node.
  3. * public class TreeNode {
  4. * int val;
  5. * TreeNode left;
  6. * TreeNode right;
  7. * TreeNode(int x) { val = x; }
  8. * }
  9. */
  10. class Solution {
  11. int sum = 0;
  12. public TreeNode convertBST(TreeNode root) {
  13. convert(root);
  14. return root;
  15. }
  16. public void convert(TreeNode root) {
  17. if (root == null) { return ; }
  18. convert(root.right);
  19. root.val += sum;
  20. sum = root.val;
  21. convert(root.left);
  22. }
  23. }
 友情链接:直通硅谷  点职佳  北美留学生论坛

本站QQ群:前端 618073944 | Java 606181507 | Python 626812652 | C/C++ 612253063 | 微信 634508462 | 苹果 692586424 | C#/.net 182808419 | PHP 305140648 | 运维 608723728

W3xue 的所有内容仅供测试,对任何法律问题及风险不承担任何责任。通过使用本站内容随之而来的风险与本站无关。
关于我们  |  意见建议  |  捐助我们  |  报错有奖  |  广告合作、友情链接(目前9元/月)请联系QQ:27243702 沸活量
皖ICP备17017327号-2 皖公网安备34020702000426号