利用go语言判断是否是完全二叉树

2024-04-02 19:55

短信预约 -IT技能 免费直播动态提醒

一、什么是完全二叉树？

先看如下这一张图：

这个一颗二叉树，如何区分该树是不是完全二叉树呢？

当一个节点存在右子节点但是不存在左子节点这颗树视为非完全二叉树
当一个节点的左子节点存在但是右子节点不存在视为完全二叉树
如果没有子节点，那也是要在左侧开始到右侧依次没有子节点才视为完全二叉树,就像上图2中

而上面第一张图这颗二叉树很明显是一颗非完全二叉树，因为在第三层也就是在节点2它并没有右子节点。在6和4节点中隔开了一个节点(2节点没有右子节点)，所以不是完全二叉树

再看第二张图，这颗树就是一个完全二叉树，虽然在这个颗节点3没有右子节点，但是6 4 5节点之间并没有空缺的子节点，这里就解释了上面说的第三条(如何没有子节点，那也是在左侧开始到右侧依次没有子节点才视为完全二叉树)

二、流程

这道题可以使用按层遍历的方式来解决：

首先准备一个队列，按层遍历使用队列是最好的一种解决方法
首先将头节点加入到队列里面(如果头节点为空，你可以认为它是一个非完全二叉树也可以认为它是完全二叉树)
遍历该队列跳出遍历的条件是直到这个队列为空时
这个时候需要准备一个Bool的变量，如果当一个节点的左子节点或者右子节点不存在时将其置成true
当Bool变量为true并且剩余节点的左或右子节点不为空该树就是非完全二叉树
当一树的左子节点不存在并且右子节点存在,该树也是非完全二叉树

三、代码

1.树节点

type TreeNode struct {
	val   string
	left  *TreeNode
	right *TreeNode
}

2.测试代码

func main() {
	root := &TreeNode{val: "1"}
	root.left = &TreeNode{val: "2"}
	root.left.left = &TreeNode{val: "4"}
	root.left.right = &TreeNode{val: "10"}
	root.left.left.left = &TreeNode{val: "7"}
	root.right = &TreeNode{val: "3"}
	root.right.left = &TreeNode{val: "5"}
	root.right.right = &TreeNode{val: "6"}
	if IsCompleteBt(root) {
		fmt.Println("是完全二叉树")
	} else {
		fmt.Println("不是完全二叉树")
	}
}

3.判断树是否为完全二叉树代码

// IsCompleteBt 这里默认根节点为空属于完全二叉树,这个可以自已定义是否为完全二叉树
func IsCompleteBt(root *TreeNode) bool {
	if root == nil {
		return true
	}

	
	var tempNodeQueue []*TreeNode

	tempNodeQueue = append(tempNodeQueue, root)

	var tempNode *TreeNode
	isSingleNode := false
	for len(tempNodeQueue) != 0 {
		tempNode = tempNodeQueue[0]
		tempNodeQueue = tempNodeQueue[1:]

		if (isSingleNode && (tempNode.left != nil || tempNode.right != nil)) || (tempNode.left == nil && tempNode.right != nil){
			return false
		}

		if tempNode.left != nil{
			tempNodeQueue = append(tempNodeQueue,tempNode.left)
		}else{
			isSingleNode = true
		}

		if  tempNode.right != nil {
			tempNodeQueue = append(tempNodeQueue, tempNode.right)
		}else{
			isSingleNode = true
		}
	}
	return true
}