二叉树的完全性检验——Python实现（BFS）

题目：给定一个二叉树，确定它是否是一个完全二叉树。百度百科中对完全二叉树的定义如下： 若设二叉树的深度为 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