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

题目描述

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 ## 正向时为访问右节点