golang中怎么利用leetcode 恢复二叉搜索树
一、什么是二叉搜索树
二叉搜索树(Binary Search Tree),又称二叉查找树、有序二叉树,是指一棵空树或者具有下列性质的二叉树:
1、若任意节点的左子树不空,则左子树上所有节点的值均小于它的根节点的值;
2、若任意节点的右子树不空,则右子树上所有节点的值均大于它的根节点的值;
3、任意节点的左、右子树也分别为二叉查找树;
4、没有键值相等的节点。
二、leetcode恢复二叉搜索树的原理
leetcode恢复二叉搜索树的原理是:首先,中序遍历二叉树,将其节点值存入一个数组中;其次,对数组进行排序;最后,再次中序遍历二叉树,将排序后的数组中的值依次赋值给二叉树节点。
三、leetcode恢复二叉搜索树的代码实现
下面是leetcode恢复二叉搜索树的golang实现代码:
package 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实现代码,它的实现原理是:首先,使用中序遍历二叉树,将其节点值存入一个数组中;其次,对数组进行排序;最后,再次中序遍历二叉树,将排序后的数组中的值依次赋值给二叉树节点。
猜您想看
-
哪些手机型号支持刷机?
刷机,即重新安...
2024年05月29日 -
如何理解Java内部类中的成员内部类
成员内部类的概...
2023年07月21日 -
怎么搭建Python开发环境
1.安装Pyt...
2023年05月26日 -
电脑关机后无法正常启动怎么办?
电脑关机后无法...
2023年05月03日 -
为什么我的电脑无法从CD或DVD中启动?
如何解决电脑无...
2023年05月03日 -
MySQL的事务和锁管理
MySQL的事...
2023年05月05日