欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

272、二叉树的完全性检验

程序员文章站 2022-03-23 17:54:56
...

题目描述:

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

百度百科中对完全二叉树的定义如下:

若设二叉树的深度为 h,除第 h 层外,其它各层 (1~h-1) 的结点数都达到最大个数,第 h 层所有的结点都连续集中在最左边,这就是完全二叉树。(注:第 h 层可能包含 1~ 2h 个节点。)

示例 1:

输入:[1,2,3,4,5,6]
输出:true
解释:最后一层前的每一层都是满的(即,结点值为 {1} 和 {2,3} 的两层),且最后一层中的所有结点({4,5,6})都尽可能地向左。
示例 2:

272、二叉树的完全性检验

输入:[1,2,3,4,5,null,7]
输出:false
解释:值为 7 的结点没有尽可能靠向左侧。

提示:

树中将会有 1 到 100 个结点。

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/check-completeness-of-a-binary-tree
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
我一开始的思路比较复杂了,先算出二叉树的层高,然后我们逐层遍历,遇见倒数第二层时需要注意
代码中写的比较冗余

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
   
    public boolean isCompleteTree(TreeNode root) {
        Queue<TreeNode> queue  = new LinkedList<>();
        int dep = getdep(root)  - 1;
        queue.offer(root);
        int curdep = 0;
        while (!queue.isEmpty()){
            if(curdep == dep){
                return true;
            }
            int size = queue.size();
            if(curdep < dep - 1){
                for (int i = 0; i < size; i++) {
                    TreeNode poll = queue.poll();
                    if(poll.left == null || poll.right == null){
                        return false;
                    }
                    queue.offer(poll.left);
                    queue.offer(poll.right);
                }
//                curdep ++;
            }else{
                boolean flag = true;
                for (int i = 0; i < size; i++) {
                    TreeNode poll = queue.poll();
                    if(poll.right != null && poll.left == null){
                        return  false;
                    }
//                    前方出现有一个
                    if((poll.left != null || poll.right != null) && !flag){
                        return false;
                    }
                    if((poll.left != null && poll.right == null) || (poll.left == null && poll.right == null)){
                        flag = false;
                    }
                    if(poll.left != null){
                        queue.offer(poll.left);
                    }
                    if(poll.right != null){
                        queue.offer(poll.right);
                    }
                }

//                curdep ++;
            }

            curdep ++;
        }
        return false;

    }
    public int getdep(TreeNode root){
        if(root == null){
            return 0;
        }
        int left = getdep(root.left);
        int right = getdep(root.right);
        return Math.max(left,right) + 1;
    }
}

看看别人实现的,简单明了
其实很简单,只要遍历到null节点,看后面有没有了,如果还有就返回false,否则为true

class Solution {
    /**
     * 广度遍历二叉树,当出现 null 值时停止遍历,如果此时还有没有遍历到的结点,说明该树非完全二叉树。
     */
    public boolean isCompleteTree(TreeNode root) {
        LinkedList<TreeNode> q = new LinkedList<>();
        TreeNode cur;
        q.addLast(root);
        while ((cur = q.removeFirst()) != null) {
            q.addLast(cur.left);
            q.addLast(cur.right);
        }
        while (!q.isEmpty()) {
            if (q.removeLast() != null) {
                return false;
            }
        }
        return true;
    }
}
相关标签: LeetCode中等