package main import . "nc_tools" import "math" /* * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */ /** * * @param root TreeNode类 the root * @return bool布尔型一维数组 */ var pre int func judgeIt(root *TreeNode) []bool { // write code here res := make([]bool, 0) pre = math.MinInt64 res = append(res, orderTravel(root)) res = append(res, bfs(root)) return res } func orderTravel(node *TreeNode) bool { if node == nil { return true } left := orderTravel(node.Left) if pre > node.Val { return false } pre = node.Val right := orderTravel(node.Right) return left && right } func bfs(node *TreeNode) bool { if node == nil { return true } leaf := false queue := make([]*TreeNode, 0) queue = append(queue, node) for len(queue) > 0 { size := len(queue) for i := 0; i < size; i++ { curr := queue[0] queue = queue[1:] //之前的节点存在右子树为空,故其余节点必须为叶子节点,否则返回false if leaf && (curr.Right != nil || curr.Left != nil) { return false } if curr.Left == nil && curr.Right != nil { return false } if curr.Left != nil { queue = append(queue, curr.Left) } if curr.Right != nil { queue = append(queue, curr.Right) } else { leaf = true } } } return true }