2020快手：判断一棵满二叉树是否为二叉搜索树[python][数据结构][树的性质]

讲真没必要那么麻烦真的去构建一棵树，直接利用二叉搜索树的性质，python十几行就结束了。

1. 满二叉树： 深度为n时共2^n-1个节点
2. 二叉搜索树： 左节点所有<=根节点<所有右节点

核心思路：中序遍历二叉搜索树应单调递增 (由题意知道节点最小值为0，因此预设pre为-1)；同时，满二叉树可以保证不越界。（BTW，如果非满，需要加一些边界条件）

pre, res = -1, True
def search(t, i):
    global pre, res
    if i >= len(t): return
    search(t, 2*i+1) # 左
    if t[i] < pre: # 非单调递增
        res = False # 找到一个反例即可证明其非二叉搜索树
        return res
    else:
        pre = t[i]
    search(t, 2*i+2) # 右

try:
    search(list(map(int, input().split(','))), 0)
except Exception as e: # 输入None根节点时直接print(True)
    pass
finally:
    print(res)