搜索二叉树，完全二叉树，平衡二叉树的判断

关注顶级算法修炼内功

顶级算法后台回复 1024 有特别礼包

责编：顶级算法 | 来源：mapleYe

链接：jianshu.com/p/b6120c8fdc8e

上一篇精彩：红黑树、B树、B+树各自适用的场景

大家好，我是顶级算法。
排序序列：
1、程序员必知必会的排序一：冒泡排序2、程序员必知必会的排序二：快速排序3、程序员必知必会的排序三：直接插入排序4、程序员必知必会的排序四：希尔排序5、程序员必知必会的排序五：拓扑排序

1、概念

搜索二叉树(Binary Search Tree - BST)

它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；

完全二叉树(Complete Binary Tree- CBT)

若设二叉树的深度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边。
经典应用：堆

平衡二叉树(Self-balancing binary search tree)

它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。
总的一句话就是，任意节点左右子树的高度差不超过1

2、搜索二叉树的判断

思路

由于搜索二叉树的特性，根节点 > 左，根节点 < 右，那么其中序遍历的顺序必然是升序的。那么我们只需在中序遍历的非递归版本，每个节点都和上一个节点比较，即可知道整个序列是否有序了。

算法实现

    /// 判断是否是搜索二叉树，就要判断是否符合左子树 < 根节点，右子树 > 根节点
    /// 而该树是搜索二叉树，那么其中序遍历必然是升序的，因此在非递归的中序遍历基础上
    /// 修改，只需对比当前数比上一个数都大，即可判断是否是搜索二叉树
    public static boolean isBST(Node head) {
        if (head == null) {
            return true;
        }
        int pre = Integer.MIN_VALUE;
        Stack<Node> stack = new Stack<Node>();
        while (!stack.isEmpty() || head != null) {
            if (head != null) {
                stack.push(head);
                head = head.left;
            }else {
                head = stack.pop();
                if (head.value < pre) {
                    return false;
                }
                pre = head.value;
                head = head.right;
            }
        }
        return true;
    }

3、完全二叉树的判断

思路

根据完全二叉树排列特性，必然先挂左边的树，可以得出以下结论：
1、如果一个树，有右孩子，没有左孩子，那么必然不是满二叉树
2、如果一个树，只有左孩子，那么后续节点必然都是叶子节点，才能是满二叉树。另外搜索公众号Java架构师技术后台回复“面试题”，获取一份惊喜礼包。

算法实现

该算法是在层级遍历的基础上，修改的。

    /// 判断是否是满二叉树
    /// 1、如果一个树，有右孩子，没有左孩子，那么必然不是满二叉树
    /// 2、如果一个树，只有左孩子，那么后续节点必然都是叶子节点，才能是满二叉树
    public static boolean isCBT(Node head) {
        if (head == null) {
            return true;
        }
        Queue<Node> queue = new LinkedList<Node>();
        queue.offer(head);
        boolean isLeaf = false;
        while(!queue.isEmpty()) {
            head = queue.poll();
            if (isLeaf) {
                if (head.left != null || head.right != null) {
                    return false;
                }
            }
            // 只有右孩子，没有左孩子，必然不是满二叉树
            if (head.left == null && head.right != null) {
                return false;
            }
            if (head.left != null && head.right == null) {
                // 开启后续节点必为叶节点的判断
                isLeaf = true;
            }
            if (head.left != null) {
                queue.offer(head.left);
            }
            if (head.right != null) {
                queue.offer(head.right);
            }
        }
        return true;
    }

4、平衡二叉树的判断

思路

由于平衡二叉树要求任意左右子树的高度差不超过1。那么，要求当前节点是否平衡，我们需要知道两个信息：
1、该节点的左右子树是否平衡
2、该节点的左右子树高度相差是否大于1
那么，我们就可以根据以上两个条件，知道了我们递归的过程中，需要判断以及返回的东西了

算法实现

在递归求二叉树的高度的基础上，做了修改

    public static boolean isBalance(Node head) {
        boolean[] res = new boolean[1];
        res[0] = true;
        getHeight(head, res);
        return res[0];
    }

    public static int getHeight(Node head, boolean[] res) {
        if (head == null) {
            return 0;
        }
        int lh = getHeight(head.left, res);
        if (!res[0]) {
            return 0;
        }
        int rh = getHeight(head.right, res);
        if (!res[0]) {
            return 0;
        }
        if (Math.abs(lh - rh) > 1) {
            res[0] = false;
        }
        return Math.max(lh, rh) + 1;
    }

觉得不错？欢迎转发分享给更多人

最近有一些小伙伴，让我帮忙找一些 面试题 资料，于是我翻遍了收藏的 5T 资料后，汇总整理出来，可以说是程序员面试必备！所有资料都整理到网盘了，欢迎下载！

点击👆卡片，关注后回复【面试题】即可获取

公众号后台回复 算法 或者 算法心得 有惊喜礼包！顶级算法交流群

 「顶级算法」建立了读者算法交流群，大家可以添加小编微信进行加群。欢迎有想法、乐于分享的朋友们一起交流学习。

扫描添加好友邀你进算法群，加我时注明【姓名+公司+职位】

版权申明：内容来源网络，版权归原作者所有。如有侵权烦请告知，我们会立即删除并表示歉意。谢谢。

往日分享：