牛客题目——判断是不是完全二叉树、平衡二叉树

• 题目1——判断是否为完全二叉树
• 解题思路
• 代码实现
• 题目2——判断是否为平衡二叉树
• 解题思路
• 代码实现

给定一个二叉树，确定它是否是一个完全二叉树。

完全二叉树的定义：若二叉树的深度为h，除第h层外，其它各层的结点数都达到最大个数，第h层所有叶子结点都连续集中在最左边，这就是完全二叉树。
下面样例图1、2是完全二叉树，而样例图3不是。

完全二叉树中叶子结点只能出现在最下层和次下层，且最下层的叶子结点集中在树的左部分。
具体做法如下：

• 首先判断空树一定是完全二叉树；
• 初始化一个队列辅助层次遍历，并将根结点入队；
• 逐渐访问队首结点，如果遇到某个结点为空，则进行标记，代表到了完全二叉树的最下层，如果后续还有不为空的结点，则不符合完全二叉树的性质；
• 否则，继续加入左右子节点到队列当中，等待访问 。

public class Solution {
    public boolean isCompleteTree (TreeNode root) {
       if(root == null) return true;
        boolean complete = false;
        Queue q = new LinkedList<>();
        q.add(root);
        while(!q.isEmpty()){
            //逐渐访问队首元素
            TreeNode cur = q.poll();
            //如果队首元素为空的话，表明第一次碰到空结点，进行标记
            if(cur == null){
                complete = true;
                continue;
            }
            //空结点后，还有结点，不符合二叉树性质
            if(complete) return false;
            //上述都不满足，将当前结点的左右子节点入队，等待访问
            q.add(cur.left);
            q.add(cur.right);
        }
        return true;
    }
}

给定一棵结点数为n的二叉树，判断该二叉树是否为平衡二叉树。

平衡二叉树的性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两棵子树都是一棵平衡二叉树。
下面样例图是平衡二叉树。

根据定义，如果我们能求出树的高度，然后根据左右子树高度差绝对值小于等于1，就可以判断以每个结点为根的树是否满足定义。
具体做法如下：

• 首先求出以根节点左右子树的高度，并判断其高度差绝对值是否不超过1；
• 递归判断左子树和右子树是否为平衡二叉树；
• 当三个条件同时满足时，为平衡二叉树 。

public class Solution {
    //求解树的高度
    public int getHeight(TreeNode node){
        int height = 0;
        if(node == null) return height;
        int l = getHeight(node.left);
        int r = getHeight(node.right);
        return Math.max(l,r)+1;
    }
    public boolean IsBalanced_Solution(TreeNode root) {
        if(root == null) return true;
        int l = getHeight(root.left);
        int r = getHeight(root.right);
        //高度之差大于1，不是平衡二叉树
        if(Math.abs(l-r)>1) return false;
        return IsBalanced_Solution(root.left) && IsBalanced_Solution(root.right);
    }
}