二叉树是否为搜索二叉树和完全二叉树

本文主要是介绍二叉树是否为搜索二叉树和完全二叉树，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

链接

给定一棵二叉树，已经其中没有重复值的节点，请判断该二叉树是否为搜索二叉树和完全二叉树。

import java.util.Scanner;

public class Main {

    private static CBTInfo solveCBT(Node root) {
        if (root == null) {
            return new CBTInfo(0, true, true);
        }

        CBTInfo leftInfo = solveCBT(root.left);
        CBTInfo rightInfo = solveCBT(root.right);

        if (leftInfo.height == rightInfo.height) {
            return new CBTInfo(leftInfo.height + 1, leftInfo.isFull && rightInfo.isFull,
                    leftInfo.isFull && rightInfo.isCBT);
        } else {
            if (leftInfo.height == rightInfo.height + 1) {
                return new CBTInfo(leftInfo.height + 1, false,
                        leftInfo.isCBT && rightInfo.isFull);
            } else {
                return new CBTInfo(rightInfo.height + 1, false, false);
            }
        }
    }

    private static BSTInfo solveBST(Node root) {
        if (root == null) {
            return new BSTInfo(true, null, null);
        }
        BSTInfo leftInfo = solveBST(root.left);
        BSTInfo rightInfo = solveBST(root.right);
        if (leftInfo.isBST && (leftInfo.mostRight == null || leftInfo.mostRight.val < root.val) &&
                rightInfo.isBST && (rightInfo.mostLeft == null || rightInfo.mostLeft.val > root.val)) {
            return new BSTInfo(true, leftInfo.mostRight == null ? root : leftInfo.mostRight,
                    rightInfo.mostRight == null ? root : rightInfo.mostRight);
        }
        return new BSTInfo(false, leftInfo.mostRight == null ? root : leftInfo.mostRight,
                rightInfo.mostRight == null ? root : rightInfo.mostRight);
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

        while (in.hasNext()) {
            int n = in.nextInt();
            Node[] nodes = new Node[n + 1];
            for (int i = 1; i <= n; ++i) {
                nodes[i] = new Node(i);
            }
            Node root = nodes[in.nextInt()];
            for (int i = 1; i <= n; ++i) {
                int fa = in.nextInt();
                nodes[fa].left = nodes[in.nextInt()];
                nodes[fa].right = nodes[in.nextInt()];
            }

            BSTInfo bstInfo = solveBST(root);
            CBTInfo cbtInfo = solveCBT(root);
            System.out.println(bstInfo.isBST);
            System.out.println(cbtInfo.isCBT);
        }
    }
}

class Node {
    Node left;
    Node right;
    int val;

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

class CBTInfo {
    int height;
    boolean isFull;
    boolean isCBT;


    public CBTInfo(int height, boolean isFull, boolean isCBT) {
        this.height = height;
        this.isFull = isFull;
        this.isCBT = isCBT;
    }
}

class BSTInfo {
    boolean isBST;
    Node mostLeft;
    Node mostRight;

    public BSTInfo(boolean isBST, Node mostLeft, Node mostRight) {
        this.isBST = isBST;
        this.mostLeft = mostLeft;
        this.mostRight = mostRight;
    }
}

这篇关于二叉树是否为搜索二叉树和完全二叉树的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！