判断给定的二叉树是否为二分查找树。假设树的每个节点以整数为键值,且不同节点的键值互不相等。二分查找树成立的判定条件:
对任何非叶子节点A,如果A存在左子树,则A的键值大于其左子树所有节点的键值,且,如果A存在右子树,则A的键值小于其右子树所有节点的键值
判断给定的二叉树是否为二分查找树。假设树的每个节点以整数为键值,且不同节点的键值互不相等。二分查找树成立的判定条件:
对任何非叶子节点A,如果A存在左子树,则A的键值大于其左子树所有节点的键值,且,如果A存在右子树,则A的键值小于其右子树所有节点的键值
第一行:根节点键值;
第二行开始,二叉树的结构,每行代表一组根节点与左右子节点的对应关系,-1代表空节点。格式:
根节点键值:左子节点键值|右子节点键值
例如,
5:3|-1
表示键值为5的节点,左子节点的键值为3,右子节点为空节点
假设:所有节点的键值非负,且不超过1023
判断结果,0表示输入不是二分查找树,1表示输入是二分查找树
5 5:4|7 4:3|8 7:2|-1 3:-1|-1 8:-1|-1 2:-1|-1
0
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 }