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

题解

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

示例代码(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)
}