判断是否为完全二叉树

梦里梦外; 2023-01-11 09:23 145阅读 0赞

## 解题思路 ##

完全二叉树看起来就是一个“满二叉树右下角缺了一块”

需要引入一个标志位来区分两个阶段

针对一个完全二叉树，进行层序遍历，会出现两种阶段  
**1）任何一个节点都一定有左子树和右子树。**  
当遇到某个节点只有左子树没有右子树的时候，那么就切换到第二阶段；  
如果只有右子树没有左子树的时候，那么就一定不是二叉树  
**2)任何一个节点，一定没有子树**

当遍历符合以上要求的时候，整个树就是完全二叉树

## 代码实现 ##

import java.util.LinkedList;
    import java.util.Queue;
    
    class TreeNode {
        
        public int val;
        public TreeNode left;
        public TreeNode right;
    
        public TreeNode(int val) {
        
            this.val = val;
        }
    }
    public class TestTree {
        
        //判断是否为完全二叉树
        public boolean isCompleteTree(TreeNode root){
        
            if (root == null){
        
                return true;
            }
            boolean isSecondStep = false;//第二阶段
            //针对这个树做层序遍历
            Queue<TreeNode> queue = new LinkedList<>();
            queue.offer(root);
            while (!queue.isEmpty()){
        
                TreeNode cur = queue.poll();
                if (!isSecondStep){
        
                    //这是第一阶段
                    //要求做右节点必须都得非空
                    if (cur.left != null && cur.right != null){
        
                        //直接把这两个字数入队列
                        queue.offer(cur.left);
                        queue.offer(cur.right);
                    }else if (cur.left == null && cur.right != null){
        
                        return false;
                    }else if (cur.left != null && cur.right == null){
        
                        //切换到第二阶段
                        isSecondStep = true;
                        queue.offer(cur.left);
                    }else {
        
                        //左右节点都为空，也要换到第二阶段
                        isSecondStep = true;
                    }
                }else {
        
                    //这是第二阶段
                    //要求任何一个节点都必须没有子树
                    if (cur.left != null || cur.right != null){
        
                        return false;
                    }
                }
            }
            return true;
            //整个树都遍历完了，返回true
        }
    
    }