Python

康斯坦奇

Python的常规做法：利用二叉搜索树的中序遍历数组为递增数组的性质。

class Node():
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None
def buildtree(nums, i):
    if i>=len(nums) or nums[i] == 'None':
        return None
    new_node = Node(nums[i])
    new_node.left = buildtree(nums, 2*i + 1)
    new_node.right = buildtree(nums, 2*i + 2)
    return new_node
def PrintIf(pRoot):
    if pRoot == None:
        return True
    val = []
    result = []
    result = midTreverse(val,pRoot)
    pre = result[0]
    for i in range(1,len(result)):
        if result[i] <= pre:
            return False
        else:
            pre = result[i]
    return True
def midTreverse(val,root):
    if root == None:
        return
    midTreverse(val,root.left)
    val.append(int(root.val))
    midTreverse(val,root.right)
    return val
if __name__ == "__main__":
    s = input()
    s_list = s.split(",")
    if len(s_list) == 1:
        print(True)
    else:
        result = []
        root = buildtree(s_list, 0)
        result=PrintIf(root)
        print(result)

发表于 2019-08-19 22:25:36 回复(3)

ChessC


	//BST性质为中序遍历递增



	//那么给定的是层序，可以考虑先构建这棵树后再LDR



	#include <bits/stdc++.h>



	usingnamespacestd;



	structTreeNode{



	    intval;



	    TreeNode* left;



	    TreeNode* right;



	    TreeNode(intx):val(x),left(NULL),right(NULL){}



	};



	classSolution{



	public:



	    vector<int> solve(TreeNode* root){



	        if(!root)



	            returnres;



	        LDR(root);



	        returnres;



	    }



	private:



	    vector<int> res;



	    voidLDR(TreeNode* root){



	        if(!root)



	            return;



	        LDR(root->left);



	        res.push_back(root->val);



	        LDR(root->right);



	    }



	};



	intmain(){



	    string s;



	    getline(cin,s); //一行读入然后逗号分隔



	    stringstream input(s);



	    vector<int> nums; //节点数组



	    string temp;



	    while(getline(input,temp,',')){



	        if(temp=="None")



	            nums.push_back(-1); //-1表示空



	        else



	            nums.push_back(stoi(temp));



	    }



	    //来生成节点



	    vector<TreeNode*> nodes;



	    for(inti=0;i<nums.size();++i){



	        if(nums[i]==-1)



	            nodes.push_back(NULL);



	        else



	            nodes.push_back(newTreeNode(nums[i]));



	    }



	    //相连即可



	    for(inti=0;i<nums.size();++i){



	        if(2*i+1<nums.size())



	            nodes[i]->left=nodes[2*i+1];



	        if(2*i+2<nums.size())



	            nodes[i]->right=nodes[2*i+2];



	    }



	    TreeNode* root=nodes[0];



	    //下面来LDR，判断是否是递增



	    Solution sol;



	    vector<int> res=sol.solve(root);



	    for(inti=1;i<res.size();++i){



	        if(res[i]<res[i-1]){



	            cout<<"False"<<endl;



	            return0;



	        }



	    }



	    cout<<"True"<<endl;



	    return0;



	}

发表于 2019-04-28 17:01:45 回复(0)

蜗牛Gray

既然是二叉搜索树，且为满树，则该二叉树可以用数组存储。

利用几个特殊的性质，节点总数为n：

1. 数组中第i个元素对应的结点，其父节点下标为 (i-1)/2，左节点 2*i+1，右节点 2*i+2

2. 所有的叶子节点，位于数组第 n/2 到 n-1.

3. 二叉搜索树中，左节点小于父节点，右节点不小于父节点

4. 左子树上的所有节点必须根节点，则节点i的左右子节点必然小于节点i的父节点p，即 (l-p)*(r-p)>0。右子树同理。

// 根据搜索二叉树和满二叉树的性质判断
// 数量 2^depth -1 = n
// n/2 ~ n-1
// parent (i-1)/2, left=2i+1, right=2i+2

#include <vector>
(721)#include <iostream>

using namespace std;

bool IsBST(vector<int> tree)
{
    if (tree.size() < 2) return true;
    
    int len = tree.size();
    int i = 0;
    int p,l,r;
    while(i < len >> 1)
    {
        l = 2*i+1;
        r = 2*i+2;
        
        if (tree[l] >= tree[i] || tree[r] < tree[i])
            return false;
        if (i)
        {
            // 子节点必须同时大于或小于父节点的父节点
            p = (i-1)/2;
            int dot = (tree[l] - tree[p]) * (tree[r] - tree[p]);
            if ( dot < 0)
                return false;
        }
        i++;
    }
    return true;
}

int main()
{
    vector<int> tree;
    
    char sep;
    int tmp;
    while (cin >> tmp >> sep)
    {
        tree.push_back(tmp);
    }
    cin >> tmp;
    tree.push_back(tmp);
    
    bool res = IsBST(tree);
    cout << (res ? "True" : "False") << endl;
    return 0;
}

发表于 2020-04-09 23:22:31 回复(2)

勇敢牛牛，不怕困难！

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

const int MAX_N = 1E5;

typedef int ElemType;
typedef struct TreeNode {
  ElemType val;
  struct TreeNode* left;
  struct TreeNode* right;
} TreeNode, *PTreeNode;

// ==================== function definition ==================== 
PTreeNode buildTree(int* tree, int sz, int index) {
  // recursion exit condition
  if (index >= sz) return NULL;
  
  PTreeNode root = malloc(sizeof(TreeNode));
  root->val   = *(tree + index);
  root->left  = buildTree(tree, sz, (index << 1) + 1);
  root->right = buildTree(tree, sz, (index << 1) + 2);
  return root;
}

void preorderTraversal(PTreeNode root) {
  if (!root) return;
  printf("%d, ", root->val);
  preorderTraversal(root->left);
  preorderTraversal(root->right);
}

int isValidBST(PTreeNode root, int low, int high) {
  if (!root) return 1;
  if (root->val <= low || root->val >= high)
    return 0;
  return isValidBST(root->left, low, root->val)
      && isValidBST(root->right, root->val, high);
}
// ==================== function definition ==================== 

int main(const int argc, const char** argv) {
  char input[(int) 5E4];
  gets(input);
  
  int tree[MAX_N], sz = 0;
  char* tok = strtok(input, ",");
  while (tok) {
    *(tree + sz++) = atoi(tok);
    tok = strtok(NULL, ",");
  }
  
  PTreeNode root = buildTree(tree, sz, 0);
//   preorderTraversal(root);
  
  printf(isValidBST(root, INT_MIN, INT_MAX) ? "True" : "False");
  return 0;
}

发表于 2021-07-08 10:38:10 回复(0)

Java

牛客557909886号

import java.util.Scanner;
public class Main{
    public static boolean isBST(int[] array){
        //不建树 利用满二叉树的性质直接比较大小  
        //左子树(2*i+1) 右子树(2*i+2)
        for(int i = 0; i < array.length/2; i++){
            //左子树小于根节点 右子树大于根节点
            if(array[i] > array[2*i+1] && array[i] < array[2*i+2]){
                //左子树的右子树小于父节点  右子树的左子树大于父节点
                if(i==0||(i%2==1&&array[2*i+2]<array[i/2])||(i%2==0&&array[2*i+1]>array[i/2-1]))
                   continue;
                else
                    return false;
            }
            else
                return false;
        }
        return true;
    }
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        String input = in.nextLine();
        String[] s = input.split(",");
        if("None".equals(s[0])){
            System.out.println("True");
            return;
        }
        int[] array = new int[s.length];
        for(int i = 0; i< array.length; i++){
            array[i] = Integer.valueOf(s[i]);
        }
        if(isBST(array))
            System.out.println("True");
        else
            System.out.println("False");
    }
}

发表于 2020-06-03 13:51:23 回复(0)

Java

何止hz

中序遍历，再检查遍历结果是否是单增序列，不用建树。

import java.util.ArrayList;
import java.util.Scanner;

/**
 * @Author: coderjjp
 * @Date: 2020-05-10 10:19
 * @Description:
 * @version: 1.0
 */
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String[] s = sc.nextLine().split(",");
        if ("None".equals(s[0])){
            System.out.println("True");
            return;
        }
        int tree[] = new int[s.length];
        for (int i = 0; i < s.length; i++)
            tree[i] = Integer.valueOf(s[i]);
        ArrayList<Integer> midSort = new ArrayList<>();
        midSort(tree, 0, s.length, midSort);
        for (int i = 1; i < midSort.size(); i++)
            if (midSort.get(i) < midSort.get(i-1)){
                System.out.println("False");
                return;
            }
        System.out.println("True");
    }

    private static void midSort(int[] tree, int i, int len, ArrayList<Integer> midSort) {
        if (i >= len)
            return;
        midSort(tree, 2*i+1, len, midSort);
        midSort.add(tree[i]);
        midSort(tree, 2*i+2, len, midSort);
    }
}

发表于 2020-05-10 10:57:02 回复(0)

tricoffee

#include<iostream>
#include<string>
#include<vector>
#include<cstdio>
#include<cstring> 
using namespace std;
int main()
{
    vector<int> a;
    string s;
    while(cin>>s)
	{
        if(s=="None")
        {
            cout<<"True"<<endl;
            return 0;
        }
        char *str = (char *)s.c_str();
        const char *split = ",";
        char *p = strtok(str,split);
        int tmp;
        while(p != NULL)
		{
            sscanf(p, "%d", &tmp);
            a.push_back(tmp);
            p = strtok(NULL,split);
        }
    }
    int n=a.size();
    if(n==0)
    {
        cout<<"True"<<endl;
        return 0;
    }
    if(n==3)
    {
        if(a[0]>a[1]&&a[0]<a[2])
        {
        	cout<<"True"<<endl;
		}
		else cout<<"False"<<endl;
        return 0;
    }
    int flag=0;
    int i=0;
    int j=1;
    int k=2;
    while(k<n)
    {
        if(a[i]>a[j]&&a[i]<a[k]) flag=1;
        else {flag=0; break;}
        if(i>0)
        {
           int t=(i-1)/2;
           if(i%2==1) 
           {
                if(!(a[t]>a[j]&&a[t]>a[k])) 
                {
                    flag=0;
                    break;
                } 
           }
           else
           {
               if(!(a[t]<a[j]&&a[t]<a[k])) 
               {
                   flag=0;
                   break;
               }
           } 
        }
        i+=1;
        j+=2;
        k+=2;
    }
    if(flag==1) cout<<"True"<<endl;
    else cout<<"False"<<endl;
    return 0;
}

编辑于 2020-03-26 00:04:41 回复(0)

myalpha

#二叉搜索树的中序遍历的是一个有序的序列
#则利用二叉树的非递归中序遍历，不断比较前一个节点的值是否大于后一个节点的值
class TreeNode():
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None
        
def buildTree(nums, i):
    if i>=len(nums) or nums[i] == 'None':
        return None
    root = TreeNode(nums[i])
    root.left = buildTree(nums, 2*i + 1)
    root.right = buildTree(nums, 2*i + 2)
    return root

def isBinarySearchTree(pRoot):
    if pRoot == None:
        return True
    
    stack = [] #创建一个栈来保存中序的访问节点
    p = pRoot
    pre = None #保存刚刚访问过节点的前一个节点
    isFirst = True 
    while(p != None or len(stack) !=0):
        while p != None:
            stack.append(p)
            p = p.left
        p = stack.pop()
        
        if isFirst: #第一次使得pre先指向中序遍历的第一节点，并且不比较前一个
            pre = p #节点和后一个节点的值
            isFirst = False
        else:  #比较前一个节点的值和后一个节点的值，看是否满足二叉搜索树的中序遍历的特点
            if(int(pre.val) > int(p.val)):
                return False
            pre = p
            
        p = p.right
    return True


if __name__ == "__main__":
    s = input()
    s_list = s.split(",")
    if len(s_list) == 1:
        print(True)
    else:
        root = buildTree(s_list, 0)
        result = isBinarySearchTree(root)
        print(result)

编辑于 2020-03-09 22:42:50 回复(0)

C/C++

不复回

怎么说呢？这题最坑的就是输入输出了吧！问问大家，是不是一般企业的笔试都是要自己写输入输出啊？

这题思路不难，直接利用线性结构（数组来建树），类似于实现堆的建树方式，即一个节点i的左右孩子为tree[2*i]和tree[2*i+1];如果一个树是二叉搜索树，那么需要满足 tree[2*i] < tree[i] < tree[2*i+1]且，而且，还需要考虑节点i是在其父亲i/2的左还是右子树上。如果节点i在左子树，还需要验证tree[2*i+1] < tree[i/2]; 如果在右子树上，还需要验证tree[2*i] > tree[i/2]。

#include<bits/stdc++.h>
using namespace std;
const int N = 10002;
int tree[N];
int father[N];
int main()
{
    int t = -1;
    int cnt = 1;
    char c;
    while(cin>>t){
        tree[cnt++] = t;
        cin>>c;
    }
    cnt--;
    for(int i=1;i<=cnt/2;++i){
        if( ! (tree[2*i]<tree[i] && tree[2*i+1] > tree[i])){
            cout<<"False"<<endl;
            return 0;
        }
        else if(i != 1){ //不考虑根的情况
            if(father[i] == 0 && tree[2*i+1] > tree[i/2]){
                cout<<"False"<<endl;
                return 0;
            }
            if(father[i] == 1 && tree[2*i] < tree[i/2]){
                cout<<"False"<<endl;
                return 0;
            }
        }
        //更新子节点告诉它们是在左子树还是右子树上；
        father[2*i] = 0;
        father[2*i+1] = 1;
    }
    cout<<"True"<<endl;
    return 0;
}

发表于 2020-03-05 23:14:36 回复(1)

C/C++

nbgao

#include <bits/stdc++.h>
using namespace std;

const int N = 10003;
int Min = -INT_MAX;
bool flag = true;
struct Tree{
    int val, left, right;
    Tree(int v){
        val = v;
        left = right = -1;
    }
    Tree(){}
}T[N];

void MidOrder(Tree R){
    if(R.left!=-1)
        MidOrder(T[R.left]);
    
    if(R.val > Min)
        Min = R.val;
    else
        flag = false;

    if(R.right!=-1)
        MidOrder(T[R.right]);
}

int main(){
    int x;
    cin>>x;
    Tree R(x);
    T[1] = R;
    int k=1;
    char c;
    while(cin>>c>>x){
        Tree P(x);
        k++;
        T[k] = P;
    }
    for(int i=1;i*2<k;i++){
        T[i].left = 2*i;
        T[i].right = 2*i+1;
    }
    MidOrder(T[1]);
    if(flag)
        cout<<"True"<<endl;
    else
        cout<<"False"<<endl;
    return 0;
}

发表于 2020-01-24 01:59:09 回复(0)

freezerhan

#include <bits/stdc++.h>

using namespace std;

vector <int> tree;
bool ret;

void read() {
	int num = 0;
	char ch;
	while ((ch = getchar()) != '\n') {
		if (ch != ',') {
			num = 10 * num + (ch - '0');
		} else {
			tree.push_back(num);
			num = 0;
		}
	}
	tree.push_back(num);
}

pair<int,int> dfs(int ind, int len) {
	pair<int,int> foo, bar;
	if (2 * ind <= len) {
		foo = dfs(ind * 2, len);
	} else {
		return {tree[ind], tree[ind]};
	}
	if (2 * ind + 1 <= len) {
		bar = dfs(ind * 2 + 1, len);
	} else {	
		return {tree[ind], tree[ind]};
	}
	int left_max = foo.second;
	int right_min = bar.first;
	if (left_max >= tree[ind] || right_min <= tree[ind]) {
		ret = false;
	}
	return {foo.first, bar.second};
}

int main() {
	tree.push_back(1);
	read();
	if (tree.size() == 1) {
		cout << "None" << "\n";
		return 0;
	}
	int len = tree.size() - 1;
	ret = true;
	dfs(1, len);
	puts(ret ? "True" : "False");
	return 0;
}

发表于 2019-11-29 08:59:17 回复(0)

C/C++

infiniteft

#include<iostream>
#include<vector>
#include<cstdio>
#include<string>
#include<sstream>

using namespace std;


bool check_less_target(vector<int> & nums, int parent_idx, int target)
{
    int left_idx = (parent_idx << 1) + 1;
    int right_idx = (parent_idx << 1) + 2;
    if(parent_idx >= nums.size() || left_idx >= nums.size() || right_idx >= nums.size())
        return true;
    if(nums[left_idx] > target)
        return false;
    if(nums[right_idx] > target)
        return false;
    return check_less_target(nums, left_idx, target) && check_less_target(nums, right_idx, target);
}

bool check_greater_target(vector<int> & nums, int parent_idx, int target)
{
    int left_idx = (parent_idx << 1) + 1;
    int right_idx = (parent_idx << 1) + 2;
    if(parent_idx >= nums.size() || left_idx >= nums.size() || right_idx >= nums.size())
        return true;
    if(nums[left_idx] < target)
        return false;
    if(nums[right_idx] < target)
        return false;
    return check_greater_target(nums, left_idx, target) && check_greater_target(nums, right_idx, target);
}

bool check_search_tree(vector<int> & nums,int parent_idx)
{
    int left_idx = (parent_idx << 1) + 1;
    int right_idx = (parent_idx << 1) + 2;
    if(parent_idx >= nums.size() || left_idx >= nums.size() || right_idx >= nums.size())
        return true;
    if(nums[left_idx] > nums[parent_idx])
        return false;
    if(nums[right_idx] < nums[parent_idx])
        return false;
    if(!check_less_target(nums, left_idx, nums[parent_idx]))
        return false;
    if(!check_greater_target(nums, right_idx, nums[parent_idx]))
        return false;
    return check_search_tree(nums, (parent_idx << 1) + 1) &&
        check_search_tree(nums, (parent_idx << 1) + 2);
}


int main(void)
{
    vector<int> nums;
    int num;
    char endstr;
    string str;
    cin >> str;
    if(str == string("None"))
    {
        printf("True\n");
        return 0;
    }
    istringstream is(str);
    do
    {
        endstr = '\n';
        is >> num;
        nums.push_back(num);
        is >> endstr;
    }while(endstr != '\n');
    if(check_search_tree(nums,0))
        printf("True\n");
    else
        printf("False\n");
    return 0;
}

解法2：从层次遍历种得出中序遍历，如果是二叉搜索树，中序遍历得到结果应该为有序递增数组

void infix_traverse_tree(vector<int> & nums, vector<int> & orderNums, int parent_idx)
{
    if(parent_idx >= nums.size())
        return ;
    int left_idx = ((parent_idx << 1) + 1);
    int right_idx = ((parent_idx << 1) + 2);
    infix_traverse_tree(nums, orderNums, left_idx);
    orderNums.push_back(nums[parent_idx]);
    infix_traverse_tree(nums, orderNums, right_idx);
}
bool check_stree(vector<int> &nums)
{
    vector<int> orderNums;
    infix_traverse_tree(nums, orderNums, 0);
    for(int i = 0; i < orderNums.size() - 1; i++)
    {
        if(orderNums[i] > orderNums[i + 1])
            return false;
    }
    return true;
}

int main(void)
{
    vector<int> nums;
    int num;
    char endstr;
    string str;
    cin >> str;
    if(str == string("None"))
    {
        printf("True\n");
        return 0;
    }
    istringstream is(str);
    do
    {
        endstr = '\n';
        is >> num;
        nums.push_back(num);
        is >> endstr;
    }while(endstr != '\n');
    if(check_stree(nums))
        printf("True\n");
    else
        printf("False\n");
    return 0;
}

编辑于 2019-11-11 10:15:58 回复(0)

ElonB

"""
二叉搜索树性质
"""

def fun(a, i):
    n = len(a)
    if i * 2 + 1 < n and a[i * 2 + 1] > a[i]: return False
    if i * 2 + 2 < n and a[i * 2 + 2] < a[i]: return False
    if (i * 2 + 1) * 2 + 1 < n and a[(i * 2 + 1) * 2 + 1] > a[i]: return False
    if (i * 2 + 1) * 2 + 2 < n and a[(i * 2 + 1) * 2 + 2] > a[i]: return False
    if (i * 2 + 2) * 2 + 1 < n and a[(i * 2 + 2) * 2 + 1] < a[i]: return False
    if (i * 2 + 2) * 2 + 2 < n and a[(i * 2 + 2) * 2 + 2] < a[i]: return False
    return True


if __name__ == '__main__':
    s = input().strip()
    if s == 'None':
        print("True")
    else:
        a = list(map(int, s.split(',')))
        ans = True
        for i in range(len(a) // 2):
            if not fun(a, i): ans = False
        print('True' if ans else 'False')

发表于 2019-10-02 19:03:18 回复(0)

Java

offer給我，我要回家

//Java解法

//这方法的思路是利用层序来先重构二叉树，然后再判断是不是二叉搜索树

运行时间：140ms

占用内存：14052k

import java.util.*;
//定义树结点
class TreeNode{
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int val){
        this.val=val;
    }
}
public class Main{
    public static void main(String[]args){
        Scanner sc=new Scanner(System.in);
       //按照顺序存放树结点，由于树结点的左、右结点还没赋值 后面会用到
        Queue<TreeNode> queue=new LinkedList<>();
        String [] str=sc.nextLine().split(",");
                //题意空树或空结点时是输入None
                //判断是否为None，空数也是二叉搜索树
        if(str[0].equals("None")){
            System.out.print("True");
            System.exit(0);
        }
                //定义根结点
        TreeNode head=new TreeNode(Integer.parseInt(str[0]));
        //再保存一个根结点，后面用来判断是否是二叉搜索树用到
                TreeNode root=head;
                //按顺序添加结点
        queue.add(head);
                //判断左结点有没有赋值
        boolean flag=false;
                //重构二叉树代码
        for(int i=1;i<str.length;i++){
                        //添加结点
            TreeNode temp=new TreeNode(Integer.parseInt(str[i]));
            queue.add(temp);
                        //如果没有给左结点赋值，则给左结点赋值
            if(!flag){
                head.left=temp;
                flag=true;
            }
                        //如果左结点赋值，则给右结点赋值
            else{
              head.right=temp;
                               //左、右结点都赋值完了，出队列
                queue.poll();
                          //重新找一个新的结点来赋值左、右结点，按入队顺序来
                head=queue.peek();
                flag=false;
            }
        }
        //找出左子树的最大值
        int max=GetMaxLeft(root.left);
                //找到右子树的最小值
        int min=GetMinRight(root.right);

                    
                //左子树的所有值都要小于根结点的值，所有找出最大值来判断
                //右子树的所有值都要大于根结点的值，所有找出最小值来判断
        //如果不满足这两个条件，直接输出False,后面都不用判断二叉搜索树了
                //不找出最值只能通过90%
                if(root.val<max||root.val>min){
            System.out.print("False");
        }
                //判断是否是二叉搜索树
        else if(check(root)){
            System.out.print("True");
        }
        else{
            System.out.print("False");
        }
    }
    //找左子树的最大值的方法
    public static int GetMaxLeft(TreeNode left){
        int max=left.val;
        LinkedList<TreeNode> list=new LinkedList<>();
        list.add(left);
        while(list.size()>0){
            TreeNode node=list.poll();
            if(node.val>max){max=node.val;}
            if(node.left!=null){
                list.add(node.left);
            }
            if(node.right!=null){
                list.add(node.right);
            }
        }
        return max;
    }
    //找右子树的最小值的方法
     public static int GetMinRight(TreeNode right){
        int min=right.val;
        LinkedList<TreeNode> list=new LinkedList<>();
        list.add(right);
        while(list.size()>0){
            TreeNode node=list.poll();
            if(node.val>min){min=node.val;}
            if(node.left!=null){
                list.add(node.left);
            }
            if(node.right!=null){
                list.add(node.right);
            }
        }
        return min;
    }
    //判断二叉搜索树的方法
        //递归
    public static boolean check(TreeNode root){
     //递归结束条件
          if(root.left==null&&root.right==null) return true;
     else if((root.left.val<root.val)&&(root.right.val>root.val)){
                return check(root.left)&&check(root.right);
            }
        else {
            return false;
        }
    }
}

编辑于 2019-09-12 00:07:26 回复(1)

十年单身换一个字节SP

import java.util.*;
public class Main{
    static class Node{
        public int data;
        public int left;
        public int right;
        public Node(int data){
            this.data = data;
            this.left = -1;
            this.right = -1;
        }
        public int getLeft(){
            return left;
        }
        public int getRight(){
            return right;
        }
        public int getData(){
            return data;
        }
    }
    private static int N  = 10001;
    private static int temp = -99999;
    private static boolean isRight = true;
    private static Node[] nodes = new Node[N];
    public static void main(String[] args){
        Scanner input = new Scanner(System.in);
        String str = input.next();
        String[] strs = str.split(",");
        int len = strs.length;
        int index=0;
        if(len==0||"None".equals(strs[0])){
            System.out.println("True");
            return;
        }
        for(int i=1;i<=len;i++){
            if(!"None".equals(strs[i-1])){
                index++;
                nodes[i]=new Node(Integer.parseInt(strs[i-1]));
            }
        }
        int pos = 1;
        while(pos*2<index){
            nodes[pos].left=pos*2;
            nodes[pos].right=pos*2+1;
            pos++;
        }
        mid(nodes[1]);
        if(isRight){
            System.out.println("True");
        }else{
            System.out.println("False");
        }
    }
    public static void mid(Node node){
        if(node.getLeft()!=-1){
            mid(nodes[node.getLeft()]);
        }
        int data = node.getData();
        if(temp<=data){
            temp=data;
        }else{
            isRight=false;
        }
        if(node.getRight()!=-1){
            mid(nodes[node.getRight()]);
        }
    }
}

主要的思路其实就是利用完全二叉树的特性，以及中序遍历的特性

如果从0开始计数的话，那么，parent=i，leftchild=i*2+1，rightchild=i*2+2；

如果从1开始计数的话，那么，parent=i，leftchild=i*2，rightchild=i*2+1；

这里我选择从1开始计数，创建一个静态内部类Node用来保存节点的信息，然后输入，这里有一个坑就是他的测试数据里面可能有None，我们别忘了判空，其实要是做笔试，这个样例就是送分的，我们应该感到高兴。然后就是分割字符串了，记得index又是一个坑，他不一定等于len，因为可能后面有多个None，然后中序遍历了，思路还是蛮简单的，但是要写完出来，确实花费了好些时间

发表于 2019-08-25 11:47:38 回复(0)

李镇强

python 常规解法

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

def buildtree(nums, i):
    if i>=len(nums) or nums[i] == 'None':
        return None
    new_node = Node(nums[i])
    new_node.left = buildtree(nums, 2*i + 1)
    new_node.right = buildtree(nums, 2*i + 2)
    return new_node

def inord(root, result):
    if root.left:
        inord(root.left, result)
    result.append(root.val)
    if root.right:
        inord(root.right, result)

if __name__ == "__main__":
    s = input()
    if s == 'None':
        print(True)
    else:
        s_list = s.split(",")
        if len(s_list) == 1:
            print(True)
        else:
            result = []
            inord(buildtree(s_list, 0), result)
            result = list(map(int, result))
            pre = result[0]
            Flag = True
            for i in range(1, len(result)):
                if result[i] <= pre:
                    Flag = False
                    break
                pre = result[i]
            print(Flag)

发表于 2019-07-26 20:17:59 回复(0)

C/C++

咖啡糖66

/*
    思路：二叉搜索树的一个性质，中序遍历是递增的。
        因此，先构建树，再中序遍历，看是否是递增的即可。
 */
#include<iostream>
#include<stdio.h>

using namespace std;

//定义树结点结构体
struct Node{
    int data;
    int left;
    int right;

    Node(int d){ 
        data = d;
        left = -1;
        right = -1;  
    }
    Node(){}
};

//一些变量
const int N = 15000;
int temp=-99999;
bool isRight = true;
Node lib[N];

//中序遍
void mid(Node node){
    if(node.left!=-1) mid(lib[node.left]);//递归左子树
    
    //比较
    int data = node.data;
    if(data>temp){
        temp = data;
    }else{//如果不是递增序列，则出错
        isRight = false;
    }
    
    if(node.right!=-1) mid(lib[node.right]);//递归右子树
}

int main(){
    
    int firstData;
    cin>>firstData;
    Node firstNode(firstData);
    lib[1] = firstNode;
    int index =1;
    int t;
    //输入结点
    while (scanf(",%d",&t)){    
            Node node(t);
            index++;
            lib[index] = node;
    }
    
    int i=1;

    //更新左右子树的编号。
    while(i*2 < index){
        lib[i].left = i*2;
        lib[i].right = i*2+1;
        i++;
    }
    
    //中序遍历
    mid(lib[1]);

    if(isRight){
        cout<<"True"<<endl;
    }else{
        cout<<"False"<<endl;
    }

    return 0;
}

发表于 2019-07-25 11:30:27 回复(0)

Nathan_Wu

//建树版
#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
using namespace std;

class TreeNode
{
public:
	int val;
	TreeNode* left;
	TreeNode* right;
	TreeNode(int v) : val(v), left(NULL), right(NULL){};
};

TreeNode* buildTree(vector<int>& nums)
{
	if (nums.size() == 0)
		return NULL;
	queue<TreeNode**> q;
	TreeNode* root = NULL;
	q.push(&root);
	for (int i = 0; i < nums.size(); i++)
	{
		*q.front() = new TreeNode(nums[i]);	
		q.push(&((*q.front())->left));
		q.push(&((*q.front())->right));
		q.pop();
	}
	return root;
}

void inOrder(TreeNode* root, vector<int>& nums)
{
	if (root)
	{
		inOrder(root->left, nums);
		nums.push_back(root->val);
		inOrder(root->right, nums);
	}
}

bool isBST(TreeNode* root)
{
	vector<int> nums;
	inOrder(root, nums);
	for (int i = 1; i < nums.size(); i++)
	if (nums[i - 1] > nums[i])
		return false;
	return true;
}

int main()
{
	int n;
	char c;
	vector<int> nums;
	while (cin >> n)
	{
		nums.push_back(n);
		cin >> c;
	}

	if (isBST(buildTree(nums)))
		cout << "True" << endl;
	else
		cout << "False" << endl;
	
	return 0;
}

//不建树版
#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
using namespace std;

void inOrder(vector<int>& nums, vector<int>& res, int curr)
{
	if ((curr * 2) < nums.size())
	{
		inOrder(nums, res, curr * 2);
	}
	res.push_back(nums[curr]);
	if ((curr * 2 + 1) < nums.size())
	{
		inOrder(nums, res, curr * 2 + 1);
	}
}

bool isBST(vector<int>& nums)
{
    if(nums.size() == 1)
        return true;
	vector<int> res;
	inOrder(nums, res, 1);
	for (int i = 1; i < res.size(); i++)
	if (res[i - 1] > res[i])
		return false;
    return true;
}

int main()
{
	int n;
	char c;
	vector<int> nums(1);
	while (cin >> n)
	{
		nums.push_back(n);
		cin >> c;
	}
    
    
	if (isBST(nums))
		cout << "True" << endl;
	else
		cout << "False" << endl;
	
	return 0;
}

编辑于 2019-11-22 14:23:01 回复(0)

C/C++

Spectre_

#include<bits/stdc++.h>
using namespace std;

// 全局变量，记录上一个节点的数值
static int preVal = INT_MIN;

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

TreeNode* buildTree(vector<int> &arr, int i) {
    if (i >= arr.size()) return nullptr;
    TreeNode *root = new TreeNode(arr[i]);
    root->left = buildTree(arr, 2 * i + 1);
    root->right = buildTree(arr, 2 * i + 2);
    return root;
}

// 判断是否为二叉搜索树
bool isBST(TreeNode *root) {
    if (root == nullptr) return true;
    bool left = isBST(root->left);
    if (!left || preVal >= root->val) return false;
    preVal = root->val;
    return isBST(root->right);
}

int main() {
    vector<int> arr;
    int a; char b;
    while (cin >> a) {
        arr.push_back(a);
        if (!(cin >> b)) break;
    }
    TreeNode *root = buildTree(arr, 0);
    cout << (isBST(root) ? "True" : "False");
    return 0;
}

发表于 2022-09-12 18:13:45 回复(0)

Java

喜欢吃火锅的三文鱼希望被offer砸中

先构建二叉树，然后判断是否为二叉搜索树

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            String[] res = sc.nextLine().split(",");
            if (res[0].equals("None")) {
                System.out.println("True");
                return;
            }

            TreeNode root = getTree(res);
            boolean flag = isBST(root);

            if (flag) {
                System.out.println("True");
            } else {
                System.out.println("False");
            }
        }
    }

    /**
    * 判断是否是二叉搜索树
    */
    static TreeNode prev = null;
    public static boolean isBST(TreeNode root) {
        if (root == null) return true;

        if (!isBST(root.left)) return false;
        if (prev != null && prev.val >= root.val) {
            return false;
        }
        prev = root;

        return isBST(root.right);
    }


    /**
    * 构建二叉树
    */
    public static TreeNode getTree(String[] res) {
        TreeNode root = new TreeNode(Integer.parseInt(res[0])), p = root;
        int idx = 0;
        Deque<TreeNode> queue = new ArrayDeque<>();
        while (p != null) {
            if (2 * idx + 1 < res.length) {
                p.left = new TreeNode(Integer.parseInt(res[2 * idx + 1]));
                queue.offer(p.left);
            }
            if (2 * idx + 2 < res.length) {
                p.right = new TreeNode(Integer.parseInt(res[2 * idx + 2]));
                queue.offer(p.right);
            }
            p = queue.poll();
            idx++;
        }

        return root;
    }
}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    public TreeNode(){}

    public TreeNode(int val) {
        this.val = val;
    }
}

发表于 2022-06-25 11:25:53 回复(0)

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

输入描述:

输出描述:

输入

输出

输入

输出

输入

输出

说明

python 常规解法

问题信息

热门推荐

通过挑战的用户

相关试题