首页 > 试题广场 >

找到搜索二叉树中两个错误的节点

[编程题]找到搜索二叉树中两个错误的节点
  • 热度指数:14802 时间限制:C/C++ 2秒,其他语言4秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
一棵二叉树原本是搜索二叉树,但是其中有两个节点调换了位置,使得这棵二叉树不再是搜索二叉树,请按升序输出这两个错误节点的值。(每个节点的值各不相同)
搜索二叉树:满足每个节点的左子节点小于当前节点,右子节点大于当前节点。
样例1图

样例2图

数据范围:,节点上的值满足 ,保证每个value各不相同
进阶:空间复杂度 ,时间复杂度
示例1

输入

{1,2,3}

输出

[1,2]

说明

如题面图    
示例2

输入

{4,2,5,3,1}

输出

[1,3]

说明:本题目包含复杂数据结构TreeNode,点此查看相关信息
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
}

发表于 2023-03-29 17:17:42 回复(0)
package main
import . "nc_tools"
/*
 * type TreeNode struct {
 *   Val int
 *   Left *TreeNode
 *   Right *TreeNode
 * }
 */

/**
 * 
 * @param root TreeNode类 the root
 * @return int整型一维数组
*/
var idx, prev, tmp int
const MIN_VALUE  = -65535
func findError( root *TreeNode ) []int {
    idx, prev, tmp = 1, MIN_VALUE, 0
    res := make([]int, 2)
    inorder(root, res)
    if idx == 0 {
        res[idx] = tmp
    }
    return res
}

func inorder(root *TreeNode, res []int)  {
    if root == nil {
        return
    }    
    inorder(root.Left, res)
    if prev != MIN_VALUE {
        if root.Val < prev {
            if idx == 1 {
                res[idx] = prev
                tmp = root.Val
            } else {
                res[idx] = root.Val
                tmp = prev
            }
            idx--
        }
    }

    prev = root.Val
    inorder(root.Right, res)
}
发表于 2021-08-14 11:04:30 回复(0)