LintCode 467 [Complete Binary Tree]

原题

检查一棵二叉树是不是完全二叉树。完全二叉树是指一棵树除了最后一层，其它层上节点都有左右孩子，最后一层上，所有节点都必须尽量靠左。

样例

    1
   / \
  2   3
 /
4

是完全二叉树

    1
   / \
  2   3
   \
    4

不是完全二叉树

解题思路

• 理清思路：
• 满二叉树：每个节点都有0或是2个孩子。
• 完全二叉树：所有的叶子都拥有同的深度，所有的内部节点拥有 2个孩子
• BFS - 广度优先搜索，对于一棵树，层层遍历，把每层的节点从左向右依此加入Stack，然后把Stack上层的None弹出，最后检查如果Stack中还有None说明不是Complete Tree
• 比如上面的不完全二叉树生成的数组为[1, 2, 3, None, 4, None, None]，将右侧None弹出后为[1, 2, 3, None, 4]，循环查找，发现还有None存在，所以是不完全二叉树

完整代码

"""
Definition of TreeNode:
class TreeNode:
    def __init__(self, val):
        this.val = val
        this.left, this.right = None, None
"""
class Solution:
    """
    @param root, the root of binary tree.
    @return true if it is a complete binary tree, or false.
    """
    def isComplete(self, root):
        # Write your code here
        if not root:
            return True
        list = [root]
        index = 0
        while index < len(list):
            if list[index]:
                list.append(list[index].left)
                list.append(list[index].right)
            index += 1
                
        while list[-1] is None:
            list.pop()
            
        for node in list:
            if node is None:
                return False
        return True