/**
* 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
}