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

package main
import . "nc_tools"
/*
 * type TreeNode struct {
 *   Val int
 *   Left *TreeNode
 *   Right *TreeNode
 * }
 */

/**
 * 
 * @param root TreeNode类 the root
 * @return bool布尔型一维数组
*/
func judgeIt(root *TreeNode) []bool {
	search, _, _ := isSearch(root)
	full := isFull(root)
	return []bool{search, full}
	// write code here
}

func isSearch(root *TreeNode) (bool, int, int) {
	if root == nil {
		return true, 0, 0
	}
	mi := root.Val
	ma := root.Val
	if root.Left != nil {
		flag, lmi, lma := isSearch(root.Left)
		if !flag || lma > root.Val {
			return false, 0, 0
		}
		mi = lmi
	}
	if root.Right != nil {
		flag, rmi, rma := isSearch(root.Right)
		if !flag || rmi < root.Val {
			return false, 0, 0
		}
		ma = rma
	}
	return true, mi, ma
}

func isFull(root *TreeNode) bool {
	if root == nil {
		return true
	}
	arr := make([]*TreeNode, 0)
	arr = append(arr, root)
	empty := false
	for len(arr) > 0 {
		tmp := make([]*TreeNode, 0)
		for _, node := range arr {
			if node.Left == nil && node.Right == nil {
				empty = true
			} else {
				if empty {
					return false
				}
				if node.Left == nil && node.Right != nil {
					return false
				} else if node.Left != nil && node.Right == nil {
					empty = true
					tmp = append(tmp, node.Left)
				} else {
					tmp = append(tmp, node.Left)
					tmp = append(tmp, node.Right)
				}
			}
		}
		arr = tmp
	}
	return true
}