判断是否为完全二叉树

小雨的分享社区

发布于 2022-10-26 06:59:53

26900

代码可运行

文章被收录于专栏：小雨的CSDN小雨的CSDN

运行总次数：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
    }

}