一棵二叉树原本是搜索二叉树,但是其中有两个节点调换了位置,使得这棵二叉树不再是搜索二叉树,请按升序输出这两个错误节点的值。(每个节点的值各不相同)
搜索二叉树:满足每个节点的左子节点小于当前节点,右子节点大于当前节点。
样例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 }