Leetcode每日一题(20200921,二叉树)

  • Post author:
  • Post category:其他

今日题目

T538 把二叉搜索树转换为累加树(简单,二叉树遍历)

题目描述

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

例如:

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

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

标签

二叉树

解析

二叉搜索树的中序遍历,遍历的顺序是值从小到大。将这个顺序倒转,我们就可以得到从大到小的遍历顺序。利用全局变量表示遍历到某个节点时,大于这个节点的节点值之和,就可以实现累加的效果。

python解法

#利用函数传值的暴力解法
class Solution:
    def convertBST(self, root: TreeNode) -> TreeNode:
        def calc(root, value):
            if not root:
                return 0
            rightVal = calc(root.right, value)
            leftVal = calc(root.left, value + root.val + rightVal)
            rootVal = root.val
            root.val += rightVal
            return rootVal + leftVal + rightVal

        calc(root, 0)
        return root
#逆向中序遍历
class Solution:
    def convertBST(self, root: TreeNode) -> TreeNode:
        sum = 0

        def reversedInorderReversal(root):
            nonlocal sum
            if not root:
                return
            reversedInorderReversal(root.right)
            sum += root.val
            root.val = sum
            reversedInorderReversal(root.left)

        reversedInorderReversal(root)
        return root

版权声明:本文为hywo_0015原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。