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实现代码,它的实现原理是:首先,使用中序遍历二叉树,将其节点值存入一个数组中;其次,对数组进行排序;最后,再次中序遍历二叉树,将排序后的数组中的值依次赋值给二叉树节点。
猜您想看
-
pyhon用.groupby()作分组运算实例代码
Python的...
2023年07月21日 -
批处理框架Spring Batch有什么用
1. Spri...
2023年07月21日 -
win10高危漏洞需要修复吗
,1. Win...
2023年05月22日 -
树莓派4B如何安装mysql5.7.28
安装前准备在开...
2023年07月22日 -
Windows7阻止用户关机的解决方法是什么
一、修改注册表...
2023年05月23日 -
Java中如何将数组转换为ArrayList
一、什么是数组...
2023年05月23日