leetcode 538. 把二叉搜索树转换为累加树

题目描述

给定一个二叉搜索树(Binary Search Tree),把它转换成为累加树(Greater Tree),使得每个节点的值是原来的节点值加上所有大于它的节点值之和。

例如:


输入: 二叉搜索树:
5
/ \
2 13

输出: 转换为累加树:
18
/ \
20 13

题解

根据二叉搜索树的特点,左子树节点的值小于根节点的值,根节点的值小于右子树节点的值,可以按照右-根-左的顺序遍历二叉树,将遍历顺序的结点的值累加起来,和当前结点的值相加

示例代码(go)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
var pre int
func convertBST(root *TreeNode) *TreeNode {
pre = 0
inorder(root)
return root
}

func inorder(root *TreeNode) {
if root == nil {
return
}
inorder(root.Right)
root.Val += pre
pre = root.Val
inorder(root.Left)
}