BST判定

[编程题]BST判定

热度指数：921 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

判断给定的二叉树是否为二分查找树。假设树的每个节点以整数为键值，且不同节点的键值互不相等。二分查找树成立的判定条件：

对任何非叶子节点A，如果A存在左子树，则A的键值大于其左子树所有节点的键值，且，如果A存在右子树，则A的键值小于其右子树所有节点的键值

输入描述:

第一行：根节点键值;

第二行开始，二叉树的结构，每行代表一组根节点与左右子节点的对应关系，-1代表空节点。格式：

根节点键值:左子节点键值|右子节点键值

例如，

5:3|-1

表示键值为5的节点，左子节点的键值为3,右子节点为空节点

假设：所有节点的键值非负，且不超过1023

输出描述:

判断结果，0表示输入不是二分查找树，1表示输入是二分查找树

示例1

输入

5
5:4|7
4:3|8
7:2|-1
3:-1|-1
8:-1|-1
2:-1|-1

输出

算法知识视频讲解

小谷围做题家

package main

import (
    "fmt"
    "os"
    "bufio"
    "strings"
    "strconv"
)

var in=bufio.NewReader(os.Stdin)

type Node struct{
    val int
    left *Node
    right *Node
}

func main() {
    var x int
    fmt.Scan(&x)
    root:=&Node{val:x}
    cnt:=map[int]*Node{x:root}
    var s string
    for{
        _,ok:=fmt.Fscan(in,&s)
        if ok!=nil{
            break
        }
        ss:=strings.Split(s,":")
        lr:=strings.Split(ss[1],"|")
        a,b,c:=atoi(ss[0]),atoi(lr[0]),atoi(lr[1])
        var node,l,r *Node
        if _,ok:=cnt[a];ok{
            node=cnt[a]
        }else{
            node=&Node{val:a}
            cnt[a]=node
        }
        if b!=-1{
            if _,ok:=cnt[b];ok{
                l=cnt[b]
            }else{
                l=&Node{val:b}
                cnt[b]=l
            }
        }
        if c!=-1{
            if _,ok:=cnt[c];ok{
                r=cnt[c]
            }else{
                r=&Node{val:c}
                cnt[c]=r
            }
        }
        node.left=l
        node.right=r
    }
    arr:=order(root)
    for i,x:=range arr{
        if i>0&&arr[i-1]>x{
            fmt.Print(0)
            return
        }
    }
    fmt.Print(1)
}

func atoi(s string)int{
    x,_:=strconv.Atoi(s)
    return x
}

func order(root *Node)[]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-18 13:17:50 回复(0)