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

判断一棵二叉树是否为搜索二叉树和完全二叉树

https://www.nowcoder.com/practice/f31fc6d3caf24e7f8b4deb5cd9b5fa97

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
}

全部评论

相关推荐

07-07 11:33
江南大学 Java
已经在暑假实习了&nbsp;,没有明确说有hc,纠结实习到八月份会不会有点影响秋招毕竟感觉今年好多提前批
程序员小白条:92的话准备提前批,其他没必要,没面试机会的,而且你要准备充分,尤其八股和算法题
点赞 评论 收藏
分享
06-28 22:48
已编辑
广东金融学院 Java
小浪_Coding:学院本+这俩项目不是buff叠满了嘛
点赞 评论 收藏
分享
昨天 13:16
湖南工学院 Java
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务