Leetcode 958. 二叉树的完全性检验

素颜马尾好姑娘i 2022-08-29 00:20 73阅读 0赞

#### 题目重述 ####

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

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

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

##### 示例 1： #####

![在这里插入图片描述][d5f9ca019c8b40a6a9f99feca1a9853f.png]

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

##### 示例 2： #####

![在这里插入图片描述][e456e45b803b4fe1ac4e3b912b4f285c.png]

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

提示：

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

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/check-completeness-of-a-binary-tree  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

#### 思路 ####

我们知道，一个结点在一个树中是由索引的，从左往右，从上往下，可以叫1，2，3，4，5，6

对于下图这样一个树  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg4OTg0MQ_size_16_color_FFFFFF_t_70]  
2结点的索引我们可以认为是3

本题核心思想在于，**判断最后结点的索引位置，是否等于树的结点个数**

整体来看，代码构成基本是**层次遍历**

#### Java实现 ####

class Solution {
        
        // 树的size 是否 等于 最后一个节点的indexCode！
        public boolean isCompleteTree(TreeNode root) {
        
            if(root == null){
        
                return true;
            }
            List<MyNode> list = new ArrayList<>();
            list.add(new MyNode(root,1));
            int i=0;
            while (i < list.size()){
        
                MyNode front = list.get(i);
                i++;
                if(front.node.left!=null){
        
                    list.add(new MyNode(front.node.left,front.indexCode*2));
                }
                if(front.node.right!=null){
        
                    list.add(new MyNode(front.node.right,front.indexCode*2 +1));
                }
            }
            return list.get(i-1).indexCode == list.size();
        }
    }
    class MyNode{
        
        public TreeNode node;
        public int indexCode;
    
        public MyNode(TreeNode node, int indexCode) {
        
            this.node = node;
            this.indexCode = indexCode;
        }
    }

[d5f9ca019c8b40a6a9f99feca1a9853f.png]: /images/20220829/56d16050c83941e98c7c38f5a88bdfe4.png
[e456e45b803b4fe1ac4e3b912b4f285c.png]: /images/20220829/9a535fdc8ba8424393da5dd8b18826ac.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg4OTg0MQ_size_16_color_FFFFFF_t_70]: /images/20220829/7937b6d64c9c44ec97cc1eaa6c2939f0.png