题解 | #判断一棵二叉树是否为搜索二叉树和完全二叉树#

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
}