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

举报
悲恋花丶无心之人 发表于 2021/02/03 00:46:30 2021/02/03
【摘要】 目录 一、题目内容 二、解题思路 三、代码 一、题目内容 给定一个二叉搜索树(Binary Search Tree),把它转换成为累加树(Greater Tree),使得每个节点的值是原来的节点值加上所有大于它的节点值之和。 例如: 输入: 原始二叉搜索树:             ...

目录

一、题目内容

二、解题思路

三、代码


一、题目内容

给定一个二叉搜索树(Binary Search Tree),把它转换成为累加树(Greater Tree),使得每个节点的值是原来的节点值加上所有大于它的节点值之和。

例如:

输入: 原始二叉搜索树:
              5
            /   \
           2     13

输出: 转换为累加树:
             18
            /   \
          20     13

二、解题思路

中序遍历,记录右节点的值,然后递归返回让根节点加上该值更新根节点,接着左节点加上更新后的根节点的值,如此递归反复。

三、代码


  
  1. # Definition for a binary tree node.
  2. class TreeNode:
  3. def __init__(self, x):
  4. self.val = x
  5. self.left = None
  6. self.right = None
  7. class Solution:
  8. def convertBST(self, root: TreeNode) -> TreeNode:
  9. cur = root
  10. self.num = 0
  11. def dfs(root):
  12. if root is not None:
  13. dfs(root.right)
  14. root.val = root.val + self.num
  15. self.num = root.val
  16. dfs(root.left)
  17. return root
  18. else:
  19. return None
  20. ans = dfs(cur)
  21. return ans
  22. if __name__ == '__main__':
  23. a = TreeNode(5)
  24. a.left = TreeNode(2)
  25. a.right = TreeNode(13)
  26. s = Solution()
  27. ans = s.convertBST(a)
  28. print(ans)

文章来源: nickhuang1996.blog.csdn.net,作者:悲恋花丶无心之人,版权归原作者所有,如需转载,请联系作者。

原文链接:nickhuang1996.blog.csdn.net/article/details/108702925

【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。