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

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

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
}

全部评论

相关推荐

真烦好烦真烦:豆包润色了自己没看看吗,再说了,都说豆包是愚蠢且勤快的大学生,ds才是聪明的研究生,怎么敢让豆包写论文的
你们的毕业论文什么进度了
点赞 评论 收藏
分享
湫湫湫不会java:先投着吧,大概率找不到实习,没实习的时候再加个项目,然后把个人评价和荣誉奖项删了,赶紧成为八股战神吧,没实习没学历,秋招机会估计不多,把握机会。或者说秋招时间去冲实习,春招冲offer,但是压力会比较大
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

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