欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

二叉树的完全性检验——Python实现(BFS)

程序员文章站 2024-01-19 10:03:04
题目:给定一个二叉树,确定它是否是一个完全二叉树。百度百科中对完全二叉树的定义如下: 若设二叉树的深度为 h,除第 h 层外,其它各层 (1~h-1) 的结点数都达到最大个数,第 h 层所有的结点都连续集中在最左边, 这就是完全二叉树。(注:第 h 层可能包含 1~2h个节点。)1、解题思路:(1)从完全二叉树的定义来看,除了最后一层以外,其它层的元素个数应该是达到最大的。(2)对于最后一层的元素,所有的元素必须全部靠左(3)按以上所述,如果可以获取每一层的元素,那么就可以获取每一层大大.....

题目:给定一个二叉树,确定它是否是一个完全二叉树。百度百科中对完全二叉树的定义如下: 若设二叉树的深度为 h,除第 h 层外,其它各层 (1~h-1) 的结点数都达到最大个数,第 h 层所有的结点都连续集中在最左边, 这就是完全二叉树。(注:第 h 层可能包含 1~ 2h 个节点。)

1、解题思路:

(1)从完全二叉树的定义来看,除了最后一层以外,其它层的元素个数应该是达到最大的。

(2)对于最后一层的元素,所有的元素必须全部靠左

(3)按以上所述,如果可以获取每一层的元素,那么就可以获取每一层大大小,从而判断是否符合条件(1)

(4)如果可以获取倒数第二层从左到右的元素,那么可以遍历判断是否满足条件(2) 根据上面的需求,可以直接采用 BFS算法

class Solution(object):
    def invertTree(self, root: TreeNode) -> int:
        if root is None or (not root.left and not root.right):
            return root

        queue = [root]
        bfs_result = [[root]]
        while queue:
            # 进行bfs 获取每一层的元素
            temp = []
            size = len(queue)
            for i in range(size):
                node = queue.pop(0)
                if node.left:
                    temp.append(node.left)
                if node.right:
                    temp.append(node.right)
            queue += temp
            if len(temp) > 0:
                bfs_result.append(temp)

        # 遍历 bfs 的结果,进行判断
        level_sum = len(bfs_result)
        for level in range(level_sum - 1):
            if len(bfs_result[level]) != 2 ** level:
                return False

        # 判断最后一层是否满足需求
        if len(bfs_result[-1]) == 2 ** (level_sum - 1):
            return True

        # 取倒数第二层进行判断,用flag作为判断当前的状态
        flag = True
        reciprocal_second = bfs_result[-2]

        # 从倒数第二层的最后一个元素向前寻找,直到第一个有子节点的元素,可以知道该元素对应的叶子节点的情况可以直接决定最后的true或者false
        while reciprocal_second:
            node = reciprocal_second.pop()
            if not node.left and not node.right:
                continue
            else:
                if not node.left:
                    flag = False
                    return flag
                else:
                    flag = True
                    break

        # 判断剩余节点是否有两个子节点,如果没有就返回false
        while reciprocal_second:
            node = reciprocal_second.pop()
            if not node.left or not node.right:
                flag = False
                break

        return flag

2、官方给出的解题思路

利用二叉树的性质,如果利用父节点和子节点间的index应该满足 right = 2 * root的关系,给所有节点编序号。 对于一颗完全二叉树,所有元素的个数应该是与序号的最后一个数字相等的。

class Solution(object):
    def invertTree(self, root: TreeNode) -> int:

        node_list = [root]
        index_list = [1]
        i = 0
        while i < len(node_list):
            node = node_list[i]
            index = index_list[i]
            if node.left:
                node_list.append(node.left)
                index_list.append(2 * index)

            if node.right:
                node_list.append(node.right)
                index_list.append(2 * index + 1)

            i += 1
        if len(node_list) == index_list[-1]:
            return True
        else:
            return False

本文地址:https://blog.csdn.net/u011412768/article/details/108243346