package binarysearchtreetogreatersumtree

import . "gitee.com/dllearn/geektime-algorithm-learn/structures"

// 1038. 从二叉搜索树到更大和树
// https://leetcode-cn.com/problems/binary-search-tree-to-greater-sum-tree/
// 注意：该题目与 538: https://leetcode-cn.com/problems/convert-bst-to-greater-tree/  相同

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

func bstToGst(root *TreeNode) *TreeNode {
	preVal = 0
	dfs(root)
	return root
}

func dfs(node *TreeNode) {
	if node != nil {
		dfs(node.Right)
		preVal = preVal + node.Val
		node.Val = preVal
		dfs(node.Left)
	}
	return
}