35.LeetCode 538. 把二叉搜索树转换为累加树

• 标签： 树
• 难度： 简单

• 题目描述

• 我的解法

先内嵌两个递归函数：tree_add(root,val)： 实现树的每个结点加上值 val ;tree_sum(root)： 返回树所有结点值之和。本解法的流程是： 先求取根节点 右子树所有结点之和,得到 sum_right，然后更新 根 节点值：root.val += sum_right, 递归地将 左 子树和 右 子树转化成累加树，对于 左 子树，其每个结点需要加上此时根节点的值，右 子树则无需改变。

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def convertBST(self, root):
        """
        :type root: TreeNode
        :rtype: TreeNode
        """
        if not root:
            return root
        
        def tree_add(root, val):
            if not root:
                return root
            tree_add(root.left,val)
            tree_add(root.right,val)
            root.val += val
            return root
        
        def tree_sum(root):
            if not root:
                return 0
            return tree_sum(root.left) + root.val + tree_sum(root.right)
            

        sum_right = tree_sum(root.right)
        root.val += sum_right
        self.convertBST(root.left)
        tree_add(root.left, root.val)
        self.convertBST(root.right)
        
        return root
        

• 其他解法

暂略。