判断一棵二叉树是否为搜索二叉树和完全二叉树_

皮蛋秀柚秋

#include<bits/stdc++.h>
using namespace std;
int InOrder(int root,int* lc,int* rc,int& pre)
{
    if(!root) return 1;
    int res = InOrder(lc[root],lc,rc,pre);
    if(root<pre) return 0;
    pre = root;
    if(res) return InOrder(rc[root],lc,rc,pre);
    else return 0;
}
int isBST(int root,int* lc,int* rc)
{
    if(!root) return 1;
    int pre = INT_MIN;
    return InOrder(root,lc,rc,pre) ? 1 : 0;
}
int isCBT(int root,int* lc,int* rc)
{
    if(!root) return 1;
    queue<int>q;
    q.push(root);
    while(!q.empty())
    {
        int cur = q.front();
        q.pop();
        if(!cur) break;
        q.push(lc[cur]);
        q.push(rc[cur]);
    }
    while(!q.empty())
    {
        if(q.front()) return 0;
        q.pop();
    }
    return 1;
}
int main()
{
    int n,root;
    cin>>n>>root;
    int p;
    int* lc = new int[n+1];
    int* rc = new int[n+1];
    for(int i=0;i<n;++i)
    {
        cin>>p;
        cin>>lc[p]>>rc[p];
    }
    cout<<(isBST(root,lc,rc) ? "true" : "false")<<endl;
    cout<<(isCBT(root,lc,rc) ? "true" : "false")<<endl;
    return 0;

}

发表于 2020-02-06 16:17:09 回复(0)

Java

pein531

二叉搜索树直接检验中序遍历序列的单调递增性即可。完全二叉树采用层次遍历的方式检验，如果遇到有右孩子没有左孩子的节点，不是完全二叉树；如果遇到一个左右孩子不双全的节点，那之后遍历的所有节点都应该是叶子节点，不满足就不是完全二叉树。

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.HashMap;
import java.util.Stack;
import java.util.LinkedList;
import java.util.Queue;

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // 构建二叉树
        String[] params = br.readLine().split(" ");
        int n = Integer.parseInt(params[0]);
        TreeNode root = new TreeNode(Integer.parseInt(params[1]));
        HashMap<Integer, TreeNode> map = new HashMap<>();
        map.put(root.val, root);
        for(int i = 0; i < n; i++){
            params = br.readLine().split(" ");
            int val = Integer.parseInt(params[0]);
            int leftVal = Integer.parseInt(params[1]);
            int rightVal = Integer.parseInt(params[2]);
            TreeNode node = map.get(val);
            if(leftVal != 0) {
                node.left = new TreeNode(leftVal);
                map.put(leftVal, node.left);
            }
            if(rightVal != 0) {
                node.right = new TreeNode(rightVal);
                map.put(rightVal, node.right);
            }
        }
        // 判断二叉搜索树
        System.out.println(isBST(root));
        // 判断完全二叉树
        System.out.println(isCBT(root));
    }

    private static boolean isBST(TreeNode root) {
        int prev = Integer.MIN_VALUE;
        Stack<TreeNode> stack = new Stack<>();
        while(!stack.isEmpty() || root != null){
            while(root != null){
                stack.push(root);
                root = root.left;
            }
            if(!stack.isEmpty()){
                root = stack.pop();
                if(root.val <= prev) return false;      // 破坏了中序遍历的单调递增特性，直接返回false
                else prev = root.val;
                root = root.right;
            }
        }
        return true;
    }
    
    private static boolean isCBT(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        boolean flag = false;      // 孩子不双全的节点是否出现过
        while(!queue.isEmpty()){
            TreeNode node = queue.poll();
            if(node.left == null && node.right != null) return false;     // 有右孩子没有左孩子
            if((node.left != null || node.right != null) && flag) return false;     // 出现过左右孩子不双全的节点，之后必须全部是叶子节点
            if(node.left == null || node.right == null) flag = true;     // 遇到左右孩子不双全的节点
            if(node.left != null) queue.offer(node.left);
            if(node.right != null) queue.offer(node.right);
        }
        return true;
    }
}

发表于 2021-11-14 13:56:24 回复(0)

C/C++

GoopherWinner_ziber

贴一个用c写的吧

#include <stdlib.h>
#include <stdbool.h>
typedef struct Ralate{
    int lc,rc;
}Ralate;

typedef struct BTNode{
    int num;
    struct BTNode *lc,*rc;
}BTNode;

int seqn[500000],k;
void CreateBTree(Ralate rec[],BTNode *addr[],int root){
    if (root==0)
        return;
    BTNode *t=addr[root];
    if (rec[root].lc) {
        BTNode *p1=(BTNode*)malloc(sizeof(BTNode));
        addr[rec[root].lc]=p1;
        p1->num=rec[root].lc;
        p1->lc=NULL;
        p1->rc=NULL;
        t->lc=p1;
        CreateBTree(rec, addr, rec[root].lc);
    }
    else
        t->lc=NULL;
    if (rec[root].rc) {
        BTNode *p2=(BTNode*)malloc(sizeof(BTNode));
        addr[rec[root].rc]=p2;
        p2->num=rec[root].rc;
        p2->lc=NULL;
        p2->rc=NULL;
        t->rc=p2;
        CreateBTree(rec, addr, rec[root].rc);
    }
    else
        t->rc=NULL;
}

void InOrdTraverse(BTNode *T){
    if (!T)
        return;
    InOrdTraverse(T->lc);
    seqn[k++]=T->num;
    InOrdTraverse(T->rc);
}

bool JudgeBST(BTNode *T){
    //利用中序考察是否为搜索二叉树(Binary Search Tree)
    //原理:搜索二叉树中序遍历序列依次递增
    void InOrdTraverse(BTNode *);
    bool s=true;
    InOrdTraverse(T);
    for (int i=1; i<k; i++) {
        if (seqn[i]<seqn[i-1]) {
            s=false;
            break;
        }
    }
    return s;
}

bool JudgeCBT(BTNode *T){
    //利用层序考察是否为完全二叉树(Complete Binary Tree)
    //原理:完全二叉树层序遍历序列有效结点位置连续(可视结点空指域为0即非有效值)
    BTNode *leseqn[500001];
    int front=-1,rear=-1;
    leseqn[++rear]=T;
    while (rear!=front) {
        BTNode *t=leseqn[++front];
        if (!t)
            continue;
        if (t->lc) {
            leseqn[++rear]=t->lc;
            if (!leseqn[rear-1])
                return false;
        }
        else
            leseqn[++rear]=NULL;
        if (t->rc) {
            leseqn[++rear]=t->rc;
            if (!leseqn[rear-1])
                return false;
        }
        else
            leseqn[++rear]=NULL;
    }
    return true;
}

int main(){
    bool JudgeBST(BTNode *);
    bool JudgeCBT(BTNode *);
    int n,root;
    while (~scanf("%d %d",&n,&root)) {
        Ralate rec[500001];
        for (int i=0; i<n; i++) {
            int k;
            scanf("%d",&k);
            scanf("%d %d",&rec[k].lc,&rec[k].rc);
        }
        BTNode *addr[500001];
        addr[0]=NULL;
        BTNode *T=(BTNode*)malloc(sizeof(BTNode));
        addr[root]=T;
        T->num=root;
        T->lc=NULL;
        T->rc=NULL;
        CreateBTree(rec, addr, root);
        k=0;
        bool s1=JudgeBST(T);
        bool s2=JudgeCBT(T);
        if (s1)
            printf("true\n");
        else
            printf("false\n");
        if (s2)
            printf("true\n");
        else
            printf("false\n");
    }
    return 0;
}

发表于 2020-06-06 20:39:43 回复(0)

Java

牛客873779487号

import java.util.*;
public class Main{

public static int preValue = Integer.MIN_VALUE;

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

public TreeNode() {
}

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

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

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


public static void main(String[] args){
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
int x=sc.nextInt();
TreeNode root=new TreeNode(x);
Queue<TreeNode> que=new LinkedList<>();
que.add(root);

HashMap<Integer,TreeNode> map=new HashMap<>();
map.put(root.val,root);

for(int i=0;i<n;i++){
int fa=sc.nextInt();
int l=sc.nextInt();
int r=sc.nextInt();
if(l!=0){
map.get(fa).left=new TreeNode(l);
map.put(l,map.get(fa).left);
}
if(r!=0){
map.get(fa).right=new TreeNode(r);
map.put(r,map.get(fa).right);
}
}
System.out.println(isBST1(root));
System.out.println(isCBT(root));
}



//使用中序遍历的方法改编,此方法适用head.val的值范围为Integer.MIN_VALUE<head.val<=Integer.MAX_VALUE；等于Integer.MIN_VALUE需要继续优化，
public static boolean isBST1(TreeNode head) {
if (head == null) {
return true;
}
boolean isleft = isBST1(head.left);
if (!isleft) {
return false;
} else {
if (head.val <= preValue) {
return false;
} else {
preValue = head.val;
}
}
return isBST1(head.right);
}

public static boolean isCBT(TreeNode root) {
if (root == null) {
return true;
}
Queue<TreeNode> que = new LinkedList<>();
que.add(root);
boolean key = false; //key用来指示第一次遇见了左右孩子不双全的情况没
while (!que.isEmpty()) {
int n = que.size();
for (int i = 0; i < n; i++) { //层序遍历
TreeNode node = que.poll();
if (node.left == null && node.right != null) {
return false;
}
//在key变换后，表示出现的节点只能是叶子节点
if (key) {
if (node.left != null || node.right != null) {
return false;
}
}
//第一次出现左右孩子不双全，改变key
if (node.right == null) {
key = true;
}
//往队列里面加节点
if (node.left != null) {
que.add(node.left);
}
if (node.right != null) {
que.add(node.right);
}
}
}
return true;
}

}

发表于 2022-07-10 20:28:59 回复(0)

Java

myorange

分享下我在牛客做《程序员代码面试指南》中树相关试题时构建树的方法，也就是将输入转换成树，方便使用，因为这类不少，都要构建树。

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int val) {
        this.val = val;
    }
}

/*
    private static TreeNode buildTree(Scanner sc, int n, int rootVal) {
        Map<Integer, TreeNode> map = new HashMap<>();
        while (n-- > 0) {
            int fa = sc.nextInt();
            int lch = sc.nextInt();
            int rch = sc.nextInt();
            TreeNode faNode = map.get(fa);
            if (faNode == null) {
                faNode = new TreeNode(fa);
                map.put(fa, faNode);
            }
            if (lch != 0) {
                TreeNode lchNode = map.get(lch);
                if (lchNode == null) {
                    lchNode = new TreeNode(lch);
                    map.put(lch, lchNode);
                }
                faNode.left = lchNode;
            }
            if (rch != 0) {
                TreeNode rchNode = map.get(rch);
                if (rchNode == null) {
                    rchNode = new TreeNode(rch);
                    map.put(rch, rchNode);
                }
                faNode.right = rchNode;
            }
        }
        return map.get(rootVal);
    }
 */

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int rootVal = sc.nextInt();
        TreeNode root = buildTree(sc, n, rootVal);
        System.out.println(isBST(root, new int[]{Integer.MIN_VALUE}));
        System.out.println(isCompleteBinaryTree(root));
    }

    private static boolean isCompleteBinaryTree(TreeNode root) {
        if (root == null) {
            return true;
        }
        Queue<TreeNode> que = new LinkedList<>();
        que.add(root);
        while(!que.isEmpty()) {
            int sz = que.size();
            for (int i = 0; i < sz; ++i) {
                TreeNode node = que.poll();
                if (node.left != null && node.right != null) {
                    que.add(node.left);
                    que.add(node.right);
                } else {
                    if (node.left == null && node.right != null) {
                        return false;
                    }
                    if (node.left != null) {
                        que.add(node.left);
                    }
                    while(!que.isEmpty()) {
                        TreeNode vnode = que.poll();
                        if (vnode.left != null || vnode.right != null) {
                            return false;
                        }
                    }
                    break;
                }
            }
        }
        return true;
    }

    private static boolean isBST(TreeNode root, int[] pre) {
        if (root == null) {
            return true;
        }
        if (!isBST(root.left, pre)) {
            return false;
        }
        if (pre[0] > root.val) {
            return false;
        }
        pre[0] = root.val;
        return isBST(root.right, pre);
    }


    private static TreeNode buildTree(Scanner sc, int n, int rootVal) {
        Map<Integer, TreeNode> map = new HashMap<>();
        while (n-- > 0) {
            int fa = sc.nextInt();
            int lch = sc.nextInt();
            int rch = sc.nextInt();
            TreeNode faNode = map.get(fa);
            if (faNode == null) {
                faNode = new TreeNode(fa);
                map.put(fa, faNode);
            }
            if (lch != 0) {
                TreeNode lchNode = map.get(lch);
                if (lchNode == null) {
                    lchNode = new TreeNode(lch);
                    map.put(lch, lchNode);
                }
                faNode.left = lchNode;
            }
            if (rch != 0) {
                TreeNode rchNode = map.get(rch);
                if (rchNode == null) {
                    rchNode = new TreeNode(rch);
                    map.put(rch, rchNode);
                }
                faNode.right = rchNode;
            }
        }
        return map.get(rootVal);
    }

}

发表于 2021-08-14 20:40:59 回复(0)

程序猿的浪漫

这个是入门题？我有点怀疑简单题，和中等题有多难

搞了半天，总算AC

#include <iostream>
#include <vector>
#include <queue>
using namespace std;


int v[500001][2];

bool isSearch(int root){
    if(root == 0){
        return true;
    }
    if((v[root][0] != 0 && v[root][0] > root) \
       ||(v[v[root][0]][1] != 0) && root < v[v[root][0]][1] ){
        return false;
    }
    
    if((v[root][1] != 0 && v[root][1] < root) || \
      (v[v[root][1]][0] != 0 && root >v[v[root][1]][0] ) ){
        return false;
    }
    return isSearch(v[root][0]) && isSearch(v[root][1]);
}

bool isAll(int root){
    queue<int>que;
    que.push(root);
    while(!que.empty()){
        int top = que.front();
        que.pop();
        if(v[top][0]){
            que.push(v[top][0]);
        }
        if(v[top][1]){
            que.push(v[top][1]);
        }
        
        if((v[top][0] == 0 && v[top][1]==0) \
          || (v[top][0] != 0 && v[top][1] ==0) ){
            while(!que.empty()){
                int t = que.front();
                que.pop();
                if(v[t][0] != 0 || v[t][1] != 0){
                    return false;
                }
            }
        }
    }
    return true;
}
int main(){
    int n,root;
    cin>>n>>root;
    for(int i = 0;i<n;++i){
        int p;
        cin>>p;
        cin>>v[p][0];
        cin>>v[p][1];
    }
    if(isSearch(root)){
        cout<<"true"<<endl;
    }else{
        cout<<"false"<<endl;
    }
    
    if(isAll(root)){
        cout<<"true"<<endl;
    }else{
        cout<<"false"<<endl;
    }
    return 0;
}

发表于 2020-07-06 16:56:04 回复(0)

gapex

Morris中序与层序遍历，偏不建立链式二叉树

#include <bits/stdc++.h>

using namespace std;

bool is_bst(vector<int> &lefts, vector<int> &rights, int root){
    int node;
    int pre = INT_MIN;
    int res = true;
    while(root){
        if((node = lefts[root])){
            while(rights[node] && rights[node] != root){
                node = rights[node];
            }
            if(rights[node] == 0){
                rights[node] = root;
                root = lefts[root];
                continue;
            }else{
                rights[node] = 0;
            }
        }
        if(pre > root && res == true) res = false;
        pre = root;
        root = rights[root];
    }
    return res;
}

bool is_cbt(vector<int> &lefts, vector<int> &rights, int root){
    if(root == 0) return true;
    queue<int> q;
    q.push(root);
    bool leaf = false;
    while(!q.empty()){
        root = q.front();
        q.pop();
        int lch = lefts[root], rch = rights[root];
        if(leaf && (lch || rch)) return false;
        if(lch) q.push(lch);
        if(rch) q.push(rch);
        else leaf = true;
    }
    return true;
}

int main(){
    int n, root;
    cin >> n >> root;
    vector<int> lefts(n + 1), rights(n + 1);
    int node, lch, rch;
    while(cin >> node >> lch >> rch){
        lefts[node] = lch;
        rights[node] = rch;
    }

    cout << boolalpha << is_bst(lefts, rights, root) << endl;
    cout << boolalpha << is_cbt(lefts, rights, root) << endl;
    return 0;
}

发表于 2020-06-29 15:13:53 回复(0)

包子冲汤胡辣汤

#include<cstdio>
#include<queue>
#include<vector>
using namespace std;
struct node{
    int lchild;
    int rchild;
};
vector<node> v;
vector<int> v1;
int j0=1;
void inorder(int node){
    if(node==0||j0==0)
        return;
    inorder(v[node].lchild);
    v1.push_back(node);
    int curlen=v1.size();
    if(curlen>1&&v1[curlen-1]<v1[curlen-2])
    {
        j0=0;
        return;
    }
    inorder(v[node].rchild);
}
int judge=1;
void iscomplete(int root){
    queue<int> q;
    q.push(root);
    int flag=0;
    while(!q.empty()){
        int no=q.front();
        q.pop();
        if(no==0)
            flag=1;
        if(no!=0)
        {
            if(flag==1){
               judge=0;
               break;
            }
            q.push(v[no].lchild);
            q.push(v[no].rchild);
        }
    }
}
int main(){
    int n,root,n1,n2,n3;
    scanf("%d %d",&n,&root);
    v.resize(n+1);
    for(int i=0;i<n;++i){
        scanf("%d %d %d",&n1,&n2,&n3);
        v[n1].lchild=n2;
        v[n1].rchild=n3;
    }
    inorder(root);
    if(j0==1){ 
        printf("true\n");
    }else{
        printf("false\n");
    }
    iscomplete(root);
    if(judge==1){
        printf("true");
    }else{
        printf("false");
    }
    return 0;
}

编辑于 2020-04-05 17:13:13 回复(0)

一字一句意在言外

#include <iostream>
#include <queue>

using namespace std;

struct Integer {
    bool exist;
    int val;
};

bool is_bst_process(int root, int *fa, int *lch, int *rch, Integer lower, Integer upper)
{
    if (root == 0) return true;
    int val = root;
    if (lower.exist && lower.val >= val) return false;
    if (upper.exist && upper.val <= val) return false;
    return is_bst_process(lch[root], fa, lch, rch, lower, {true, val}) &&
           is_bst_process(rch[root], fa, lch, rch, {true, val}, upper);
}

inline bool is_bst(int root, int *fa, int *lch, int *rch)
{
    return is_bst_process(root, fa, lch, rch, {false, 0}, {false, 0});
}

inline bool is_cbt(int root, int *fa, int *lch, int *rch)
{
    queue<int> q;
    q.push(root);
    bool leaf = false;
    while (!q.empty()) {
        root = q.front(); q.pop();
        int left = lch[root], right = rch[root];
        if (!leaf && !left && right) 
            return false;
        else if (leaf && (left || right))
            return false;
            
        if (!left || !right) leaf = true;
        if (left) q.push(left);
        if (right) q.push(right);
    }
    return true;
}

int main(void)
{
    int n, root;
    cin >> n >> root;
    int *fa = new int[n + 1];
    int *lch = new int[n + 1];
    int *rch = new int[n + 1];
    int pa, lc, rc;
    for (int i = 0; i < n; i++) {
        cin >> pa >> lc >> rc;
        lch[pa] = lc;
        rch[pa] = rc;
        if (lc) fa[lc] = pa;
        if (rc) fa[rc] = pa;
    }
    cout << boolalpha << is_bst(root, fa, lch, rch) << endl;
    cout << is_cbt(root, fa, lch, rch) << endl;
    return 0;
}

发表于 2020-02-08 19:49:03 回复(0)

Java

平平无奇猪仔

import java.util.*;

class node {
    int val;
    node left, right;
    node(int val) {
        this.val = val;
    }
}

public class Main {
    private static int pre = 0;
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        node root = new node(scanner.nextInt());
        HashMap<Integer, node> map =  new HashMap<>();
        map.put(root.val, root);
        for(int i=0;i<n;i++) {
            node parent, left, right;
            parent = getNodeIfExist(map, scanner.nextInt());
            left = getNodeIfExist(map, scanner.nextInt());
            right = getNodeIfExist(map, scanner.nextInt());
            parent.left = left;
            parent.right = right;
        }

        System.out.println(isBST(root));
        System.out.println(isCBT(root));
    }
    private static boolean isBST(node root) {
        //是否二叉搜索树
        if(root == null) return true;
        boolean left = isBST(root.left);
        if(left) {
            if(pre > root.val) return false;
            pre = root.val;
        }
        return left && isBST(root.right);
    }
    private static boolean isCBT(node root) {
        //是否完全二叉树
        if(root == null) return true;
        Queue<node> queue = new LinkedList<>();
        queue.add(root);
        boolean leaf = false;
        while(queue.size() != 0) {
            node head = queue.remove();
            if(head.right != null && head.left == null) return false;
            if(head.left != null && head.right == null) {
                if(leaf) return false;
                leaf = true;
            }
            if(head.left != null) {
                queue.add(head.left);
            }

            if (head.right != null) {
                queue.add(head.right);
            }
        }
        return true;
    }
    private static node getNodeIfExist(HashMap<Integer, node> map, int val) {
        if(val == 0) return null;

        if(map.get(val) == null) {
            map.put(val, new node(val));
        }
        return map.get(val);
    }
}

第一步是建树，因为节点的值是唯一的，所以用hashmap。这样可以O1时间get到节点。

第一问BST, 中序遍历是升序的，记录前一个的值，保证升序就行。

第二问CBT，区分满二叉树和完全二叉树，满二叉树是每一层都填满，完全二叉树是满二叉树层序遍历又缺少了连续的尾部。层序遍历中，某个节点有右没有左->肯定不行；有左没有右->只能有一次，之后都必须是左右都没有。

发表于 2019-09-24 16:42:01 回复(0)

判断一棵二叉树是否为搜索二叉树和完全二叉树

输入描述:

输出描述:

输入

输出

备注:

问题信息

热门推荐

通过挑战的用户

相关试题