一棵二叉树原本是搜索二叉树,但是其中有两个节点调换了位置,使得这棵二叉树不再是搜索二叉树,请按升序输出这两个错误节点的值。(每个节点的值各不相同)
搜索二叉树:满足每个节点的左子节点小于当前节点,右子节点大于当前节点。
样例1图
样例2图
数据范围:
,节点上的值满足
,保证每个value各不相同
进阶:空间复杂度
,时间复杂度
{1,2,3}[1,2]
如题面图
{4,2,5,3,1}[1,3]
package main
import . "nc_tools"
/*
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
/**
*
* @param root TreeNode类 the root
* @return int整型一维数组
*/
func findError( root *TreeNode ) []int {
var a,b int
arr:=order(root)
for i,x:=range arr{
if i>0&&x<arr[i-1]{
if a==0{
a,b=arr[i-1],x
}else{
b=x
break
}
}
}
if a>b{
return []int{b,a}
}
return []int{a,b}
}
func order(root *TreeNode)[]int{
if root==nil{
return nil
}
ans:=[]int{}
ans=append(ans,order(root.Left)...)
ans=append(ans,root.Val)
ans=append(ans,order(root.Right)...)
return ans
}