二叉搜索树判定

[编程题]二叉搜索树判定

热度指数：2283 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 128M，其他语言256M
算法知识视频讲解

给定一个二叉树，判断其是否是一个有效的二叉搜索树。
假设一个二叉搜索树具有如下特征：
节点的左子树只包含小于当前节点的数。
节点的右子树只包含大于当前节点的数。

所有左子树和右子树自身必须也是二叉搜索树。

例如：

输入：
    5
   / \
1   3
     / \
    4   6
输出: false

二叉树节点定义如下，如果使用其他语言，其二叉树节点定义类似：
/**
* C++
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/

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

/**
* Go
* type TreeNode struct {
*     Val int
*     Left *TreeNode
*     Right *TreeNode
* }
*/

输入描述:

第一行两个数n,root，分别表示二叉树有n个节点，第root个节点时二叉树的根
接下来共n行，第i行三个数val_i,left_i,right_i，分别表示第i个节点的值val是val_i,左儿子left是第left_i个节点，右儿子right是第right_i个节点。
节点0表示空。
1<=n<=100000,保证是合法的二叉树

输出描述:

输出"true"如果给定二叉树是二叉搜索树，否则输出"false"

示例1

输入

输出

false

示例2

输入

输出

true

备注:

你可以使用以下C++代码作为模板，实现其中的isBinarySearchTree()函数。对于其它语言可类似的实现。

#include <bits/stdc++.h>

using namespace std;

struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

bool isBinarySearchTree(int n, TreeNode * root) {
// do something !

}

int main(void) {
int n,r;
scanf("%d%d",&n,&r);
TreeNode * tree, * root;
tree = (TreeNode*)malloc(sizeof(TreeNode)*(n+1));
root = &tree[r];
for (int i=1;i<=n;i++) {
int v,l,r;
scanf("%d%d%d",&v,&l,&r);
tree[i].val = v;
tree[i].left = l?&tree[l]:0;
tree[i].right = r?&tree[r]:0;
}
printf(isBinarySearchTree(n,root)?"true\n":"false\n");
return 0;
}

算法知识视频讲解

Python

康斯坦奇

Python版本的case：73.33%，AC不了，不知道为啥？

class TreeNode:
    def __init__(self,val):
        self.val = val
        self.left = None
        self.right = None
class Solution:
    def isBinarySearchTree(self,root):
        if root == None:
            return True
        result = self.midOrder(root)
        for i in range(len(result)):
            if i == len(result)-1:
                break
            if result[i] > result[i+1]:
                return False
        return True
    def midOrder(self,root):
        if root == None:
            return []
        return self.midOrder(root.left) + [root.val] + self.midOrder(root.right)
    def createTree(self,line,i):
        if i < 0:
            return None
        a,b,c = line[i]
        root = TreeNode(a)
        root.left = self.createTree(line,b-1)
        root.right = self.createTree(line,c-1)
        return root
s = Solution()
input1 = [int(x) for x in input().split()]
array = []
for i in range(input1[0]):
    input2 = [int(x) for x in input().split()]
    array.append(input2)
root= s.createTree(array,input1[1] - 1)
print('true' if s.isBinarySearchTree(root) else 'false')

发表于 2019-08-21 12:54:13 回复(2)