题解 | #判断一棵二叉树是否为搜索二叉树和完全二叉树#
判断一棵二叉树是否为搜索二叉树和完全二叉树
https://www.nowcoder.com/practice/f31fc6d3caf24e7f8b4deb5cd9b5fa97
具体逻辑请查看代码注释
package main
import . "nc_tools"
import "math"
/*
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
/**
*
* @param root TreeNode类 the root
* @return bool布尔型一维数组
*/
func isSerachTree(root *TreeNode, left int, right int) bool {
if root == nil {
return true
}
if root.Val < left || root.Val > right { // 初始时如果根节点小于左边界，或者大于有边界，则不为搜索树
return false
}
return isSerachTree(root.Left, left, root.Val) && isSerachTree(root.Right, root.Val, right) // 递归判断左子树和右子树分别是否是搜索树，
} // 往左子树传递时，左边界不变，有边界变为当前节点的值
// 往右子树传递时，有边界不变，左边界变为当前节点的值
func isTotalTree(root *TreeNode) bool {
if root == nil {
return true
}
queue := []*TreeNode{}
queue = append(queue, root)
for queue[0] != nil {
popNode := queue[0]
queue = queue[1:] //队首元素出队
queue = append(queue, popNode.Left) //将左子树入队
queue = append(queue, popNode.Right) //将右子树入队
}
for len(queue) > 0 && queue[0] == nil {
queue = queue[1:]
}
if len(queue) == 0 {
return true
}
return false
}
func judgeIt(root *TreeNode) []bool {
// write code here
minValue := math.MinInt64
maxValue := math.MaxInt64
t1 := isSerachTree(root, minValue, maxValue) // 调用时用最小值控制左边界，最大值控制右边界
t2 := isTotalTree(root)
res := []bool{}
res = append(res, t1)
res = append(res, t2)
return res
}