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

1. 题目描述

给出二叉 搜索 树的根节点，该树的节点值各不相同，请你将其转换为累加树（Greater Sum Tree），使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。

2. 思路

1. 思路一
   • 中序遍历转换成数组
   • 从最后一个元素开始往前累加
2. 思路二
   • 中序遍历反向遍历
   • 本质上和二叉搜索树的第k个结点.md差不多

3. 实现

3.1. 中序遍历转换成数组

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func convertBST(root *TreeNode) *TreeNode {
	path := make([]*TreeNode, 0)
	convertBSTDFS(root, &path)
	for i := len(path) - 2; i >= 0; i-- {
		path[i].Val += path[i+1].Val
	}
	return root
}

func convertBSTDFS(root *TreeNode, path *[]*TreeNode) {
	if root == nil {
		return
	}

	convertBSTDFS(root.Left, path)
	*path = append(*path, root)
	convertBSTDFS(root.Right, path)
}

3.2. 中序遍历反向遍历

//**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func convertBST(root *TreeNode) *TreeNode {
    sum := 0
    dfs(root, &sum)
    return root
}

func dfs(root *TreeNode, sum *int) {
    if root == nil {
        return
    }

    dfs(root.Right, sum)
    *sum += root.Val
    root.Val = *sum
    dfs(root.Left, sum)
}

4. 参考

• 「手画图解」中序遍历，反向的 538. 把二叉搜索树转换为累加树 - 把二叉搜索树转换为累加树 - 力扣（LeetCode）