java判断一颗树是不是完全二叉树

短命女 2024-03-16 12:32 13阅读 0赞

## 判断一颗树是不是完全二叉树 ##

2023 01 10 107 00 46 07  
完全二叉树的定义就不说了，那么我们如何判断一颗树是普通树还是完全二叉树呢

**题目描述**：  
给定一个二叉树的头结点TreeNode root，要求返回true或者false。

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

**代码**：  
实际就是用层序遍历的思想

boolean isCompleteTree(TreeNode root){
        
            if(root == null){
        
                return true;
            }
            Deque<TreeNode> deque = new LinkedList<>();
            deque.offer(root);
            while(!deque.isEmpty()){
        
                TreeNode cur = deque.poll();
                if(cur != null){
        
                    deque.offer(cur.left);
                    deque.offer(cur.right);
                }
                else{
        
                    break;
                }
            }
            while(!deque.isEmpty()){
        
                TreeNode cur = deque.poll();
                if(cur != null){
        
                    return false;
                }
            }return true;
        }

**测试**  
树的定义

ublic class MyBinaryTree {
        
    
        class TreeNode {
        
            char val;
            TreeNode left;
            TreeNode right;
    
            public TreeNode(char val) {
        
                this.val = val;
                this.left = null;
                this.right = null;
            }
        }
    
        public TreeNode root;//根节点
    }

Test类

public class Test {
        
        public static void main(String[] args) {
        
            MyBinaryTree myBinaryTree1 = new MyBinaryTree();
            MyBinaryTree.TreeNode root = myBinaryTree1.root;
            MyBinaryTree.TreeNode A = new MyBinaryTree().new TreeNode('A');
            MyBinaryTree.TreeNode B = new MyBinaryTree().new TreeNode('B');
            MyBinaryTree.TreeNode C = new MyBinaryTree().new TreeNode('C');
            MyBinaryTree.TreeNode D = new MyBinaryTree().new TreeNode('D');
            MyBinaryTree.TreeNode E = new MyBinaryTree().new TreeNode('E');
            MyBinaryTree.TreeNode F = new MyBinaryTree().new TreeNode('F');
            MyBinaryTree.TreeNode G = new MyBinaryTree().new TreeNode('G');
            MyBinaryTree.TreeNode H = new MyBinaryTree().new TreeNode('H');
            A.left = B;A.right = C;B.left = D;B.right = E;E.right = H;C.left = F;C.right = G;
            root = A;
            //判断是不是完全二叉树
            System.out.println("判断是不是完全二叉树");
            System.out.println(myBinaryTree1.isCompleteTree(root));
            }
     }

结果  
![在这里插入图片描述][b4c6ec356310431ab2fe4441ec5bb9ac.png]

[a76f760ac04a419ba1d0dc11b8a342c9.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/16/636da2b5f28546b28e59e477900eb8bc.png
[b4c6ec356310431ab2fe4441ec5bb9ac.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/16/01bab4785ac140aeb5e8a5cc2848c6f2.png