luoheng
10/12/2019 - 2:15 AM

convertBST

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */

func postOrder(root *TreeNode, sum int) int {
    if root == nil {
        return 0
    }
    if root.Left != nil {
        sum = postOrder(root.Left, sum)
    }
    root.Val, sum = sum, sum - root.Val
    if root.Right != nil {
        sum = postOrder(root.Right, sum)
    }
    return sum
}

func convertBST(root *TreeNode) *TreeNode {
    if root == nil {
        return nil
    }
    stack, sum := []*TreeNode{root}, 0
    for len(stack) != 0 {
        node := stack[len(stack)-1]
        stack = stack[:len(stack)-1]
        sum += node.Val
        if node.Left != nil {
            stack = append(stack, node.Left)
        }
        if node.Right != nil {
            stack = append(stack, node.Right)
        }
    }
    postOrder(root, sum)
    return root
}