Python modified inorder traversal solution


  • 0

    I use modified inorder traversal since it is a BST.
    right -> root -> left

    # 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
            """
            # right -> center -> left traverse, accumulate node value
            self.accum = 0
            self._inorder(root)
            return root
        
        def _inorder(self, node):
            if not node: return
            self._inorder(node.right)
            tmp = node.val
            node.val = node.val + self.accum
            self.accum = self.accum + tmp
            self._inorder(node.left)
            return
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.