代码实现搜索二叉树、完全二叉树

# 思路：利用递归进行中序遍历，通过判断中序遍历序列是否有序来判定是否为搜索二叉树

def isBSTmidTravelsal(self,root):

    res = []

    def dfs(root):

        nonlocal res

        if not root:

            return 

        dfs(root.left)

        res.append(root.val)

        dfs(root.right)

    dfs(root)

    return res==sorted(res)

# 层次遍历

# 使用队列，每移除一个节点就向队列添加左右节点，当遇到None时判断当前队列是否全是None,如果队列中除了None还有其它值则表示当前节点之后的节点还有左右子树即不是完全性二叉树。

def isCBT(self,root):

    q= [root]

    while q:

        for i in range(len(q)):

            node=q.pop(0)

            if  node is None:

                if set(q)=={None}:

                    return True

                else:

                    return False

# 注意这里的空节点也要进队，因此不需要进行层次序列的空节点判断

#                 if node.left:

            q.append(node.left)

#                 if node.right:

            q.append(node.right)

# newcoder完整代码

# class TreeNode:

#     def __init__(self, x):

#         self.val = x

#         self.left = None

#         self.right = None

#

# 

# @param root TreeNode类 the root

# @return bool布尔型一维数组

#

class Solution:

    def judgeIt(self , root ):

        return [self.isBSTmidTravelsal(root),self.isCBT(root)]

    def isBSTmidTravelsal(self,root):

        res = []

        def dfs(root):

            nonlocal res

            if not root:

                return 

            dfs(root.left)

            res.append(root.val)

            dfs(root.right)

        dfs(root)

        return res==sorted(res)

    def isCBT(self,root):

        q= [root]

        while q:

            for i in range(len(q)):

                node=q.pop(0)

                if  node is None:

                    if set(q)=={None}:

                        return True

                    else:

                        return False

#                 if node.left:

                q.append(node.left)

#                 if node.right:

                q.append(node.right)

#         return True

        # write code here