判断一棵满二叉树是否为二叉搜索树

class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None


def buildTree(TreeNodeList, k):
    if k >= len(TreeNodeList) or TreeNodeList[k] == 'None':
        return None
    newNode = TreeNode(TreeNodeList[k])
    newNode.left = buildTree(TreeNodeList, 2 * k + 1)
    newNode.right = buildTree(TreeNodeList, 2 * k + 2)
    return newNode


def Inorder(pRoot):
    if pRoot is None:
        return None
    else:
        Inorder(pRoot.left)
        InorderList.append(int(pRoot.val))
        Inorder(pRoot.right)


if __name__ == '__main__':
    inputList = raw_input().split(',')
    if len(inputList) == 0:
        print("False")
    root = buildTree(inputList, 0)
    InorderList = []
    Inorder(root)
    if len(InorderList) == 0:
        InorderList.append('None')
        print("True")
    else: 
        inputList = list(map(int,inputList))
        inputList.sort()
        if InorderList == inputList:
            print("True")
        else:
            print("False")

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

s=input()
if s=="None":
    print(True)
else:
    s=s.strip()
    s=s.split(",")
    arr=[]
    for tmp in s:
        arr.append(int(tmp))
    root=TreeNode(arr[0])
    cnt=1
    q=[root]
    p=[]
    for i in range(20):
        p.append(1<<i)
    if len(s)+1 not in p:
        print(False)
    else:
        while cnt<=len(arr)-1:
            node=q.pop(0)
            node.left=TreeNode(arr[cnt])
            cnt+=1
            node.right=TreeNode(arr[cnt])
            cnt+=1
            q.append(node.left)
            q.append(node.right)
        arr0=[]
        def tin(root):
            if root==None:
                return None
            tin(root.left)
            arr0.append(root.val)
            tin(root.right)
        tin(root)
        flag=True
        for i in range(len(s)-1):
            if arr0[i]>arr0[i+1]:
                flag=False
        print(flag)

这题的数据很坑，一直只能过90%。原来是有一组数据的节点数目不是2^n-1，节点数都不满足 满二叉树，巨坑。

def is_binary_search_tree(bfs, cur, flag = True):
    parent = (cur - 1) // 2 if cur >= 1 else None
    left = 2 * cur + 1
    right = 2 * cur + 2
    if left < len(bfs) and bfs[left] == "None":
        return True
    if left < len(bfs) and (bfs[left] > bfs[cur] or bfs[cur] > bfs[right]
                            or (parent is not None and flag and bfs[right] > bfs[parent])
                            or (parent is not None and not flag and bfs[left] < bfs[parent])):
        return False
    if left >= len(bfs):
        return True
    return is_binary_search_tree(bfs, left) and is_binary_search_tree(bfs, right, False)

if __name__ == "__main__":
    s = input().split(",")
    inp = []
    for i in s:
        if i == "None":
            inp.append(i)
        else:
            inp.append(int(i))
    if len(s) == 0 or len(s) == 1:
        print(True)
    else:
        s = list(map(int, s))
        print(is_binary_search_tree(s, 0))
        

python解法

---

题目的思路并不复杂。大致如下

• 根据input构建二叉树

• 中序遍历二叉树。由于二叉搜索树中序遍历元素是递增的，所以遍历时如果前一个元素大于等于后一个元素，返回False

• 若遍历完成，说明为二叉搜索树

  这里看了几个解法，发现都是遍历整棵树再去检查遍历结果是否递增。但其实在遍历的时候如果发现非递增就可以直接终止了。

  class Node:
    def __init__(self,x):
        self.val = x
        self.left = None
        self.right = None
    def getInput():
        values = input()
    try:
        values = list(map(int,values.split(",")))
        values = [Node(i) for i in values]
    except: values = None
    return values
  def buildTree(values):
    values.insert(0,None)
    for i in range(1,len(values)//2):
        values[i].left = values[2*i]
        values[i].right = values[2*i+1]
    return values[1]
  def isBST(root):
    if not root:
        return True
    if not root.left and not root.right:
        if not inTraversal:
            inTraversal.append(root.val)
            return True
        result = inTraversal[-1] < root.val
        inTraversal.append(root.val)
        return result
    if not isBST(root.left): return False
    if inTraversal[-1]>=root.val: return False
    inTraversal.append(root.val)
    if not isBST(root.right): return False
    return True
  values = getInput()
  if not values: print("True")
  else:
    root = buildTree(values)
    inTraversal = []
    print(isBST(root))