golang中怎么利用leetcode 恢复二叉搜索树

一、什么是二叉搜索树

二叉搜索树（Binary Search Tree），又称二叉查找树、有序二叉树，是指一棵空树或者具有下列性质的二叉树：

1、若任意节点的左子树不空，则左子树上所有节点的值均小于它的根节点的值；

2、若任意节点的右子树不空，则右子树上所有节点的值均大于它的根节点的值；

3、任意节点的左、右子树也分别为二叉查找树；

4、没有键值相等的节点。

二、leetcode恢复二叉搜索树的原理

leetcode恢复二叉搜索树的原理是：首先，中序遍历二叉树，将其节点值存入一个数组中；其次，对数组进行排序；最后，再次中序遍历二叉树，将排序后的数组中的值依次赋值给二叉树节点。

三、leetcode恢复二叉搜索树的代码实现

下面是leetcode恢复二叉搜索树的golang实现代码：

12345678910111213141516171819202122232425262728293031323334package main

import (
	"fmt"
)

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

func recoverTree(root *TreeNode) {
	var prev *TreeNode
	var first, second *TreeNode
	inOrder(root, &prev, &first, &second)
	first.Val, second.Val = second.Val, first.Val
}

func inOrder(root *TreeNode, prev, first, second **TreeNode) {
	if root == nil {
		return
	}
	inOrder(root.Left, prev, first, second)
	if *prev != nil && (*prev).Val > root.Val {
		if *first == nil {
			*first = *prev
		}
		*second = root
	}
	*prev = root
	inOrder(root.Right, prev, first, second)
}

func main() {
	root := &TreeNode{Val: 1}
	root.Left = &TreeNode{Val: 3}
	root.Left.Right = &TreeNode{Val: 2}
	recoverTree(root)
	fmt.Println(root.Val, root.Left.Val, root.Left.Right.Val)
}

上面的代码是leetcode恢复二叉搜索树的golang实现代码，它的实现原理是：首先，使用中序遍历二叉树，将其节点值存入一个数组中；其次，对数组进行排序；最后，再次中序遍历二叉树，将排序后的数组中的值依次赋值给二叉树节点。