Leetcode538 把二叉搜索树转换为累加树

2020年9月21日 0 作者 折纸

题目描述

file

方法一

class Solution(object):
    def convertBST(self, root):
        """
        :type root: TreeNode
        :rtype: TreeNode
        """

        ##反向中序遍历 然后把前面的值一直累加到当前节点值

        stack = []
        node = root
        val = 0

        while stack or node:
            if node:
                stack.append(node)
                node = node.right
            else:
                node = stack.pop()
                val += node.val
                node.val = val
                node = node.left
        return root

 

思路

  • v0版本 2遍DFS但是没有利用到BST的条件

  • v1版本 反向中序遍历,记录在当前节点值之前的所有节点值之和 并加到当前节点值上即可

    ###反向中序遍历
    stack,node = [],root
    while node or stack:
    if node:
        stack.append(node)
        node = node.right ##正向时为访问左节点
    else:
        node = stack.pop()
        print(node.val)
        node = node.left ## 正向时为访问右节点