《经典算法题》二叉树基础(二)

怼烎@ 2024-05-25 17:33 106阅读 0赞

## 前言: ##

**二叉树的题目绝大多数都可以利用递归来解决，熟练掌握二叉树的前中后序遍历以及层序遍历是能快速解决二叉树题目的基础。**

--------------------

**目录**

前言:

一：判断完全二叉树

1.1:思路

1.2：代码

1.3代码：

二：二叉树的最大宽度

2.1：思路

2.2: 代码1

2.2:代码2

三：二叉树的最大距离

3.1：思路

3.2:代码

--------------------

## 一：判断完全二叉树 ##

> **?：判断一颗二叉树是完全二叉树.(拓展题非力扣)**

### 1.1:思路 ###

> **?：完全二叉树的定义:除最后一层外，其它层为全满结构，且最后一层的节点全部集中在**
> 
> **左边（即最后一层是从左到右渐满的结构）。**
> 
> ![watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5b-r5LmQ55qE5pif55CD_size_20_color_FFFFFF_t_70_g_se_x_16][]

**解法一：**

**判断完全二叉树的条件：**

**（1):存在节点有右孩子但无左孩子，则一定不是完全二叉树**

**(2):在层序遍历中，遇到叶子节点后，后边遇到的所有节点均是叶子节点，如上图**

**F节点是叶子节点，则G,H,I,J全是叶子节点。如果遇到了叶子节点，后面还有非叶子节点，则一定**

**不是完全二叉树。**

### **1.2：代码** ###

//给你一个二叉树，请判断其是否为完全二叉树
        //判断规则两条
        //1:如果遇到有右孩子，无左孩子的一定不是完全二叉树
        //2:如果遇到了左右不双全的节点（即：没有左孩子和右孩子的节点）,则之后的所有点，都是叶子节点
       public static class TreeNode{
            public int val;
            public TreeNode left;
            public TreeNode right;
            public  TreeNode(int val){
                this.val=val;
            }
        }
        public static boolean isCBT(TreeNode root){
            //默认空树是完全二叉树
            if(root==null){
                return true;
            }
            //基于宽度优先遍历的判断规则
            Queue<TreeNode> queue=new LinkedList<>();
            TreeNode left=null;
            TreeNode right=null;
            boolean isMeet=false;//是否遇到了叶子节点
            queue.add(root);
            while(!queue.isEmpty()){
                TreeNode cur=queue.poll();
                left=cur.left;
                right=cur.right;
                if((right!=null&&left==null)||(isMeet&&left!=null)){
                    return false;
                }
                //设置好isMeet
                isMeet=left==null;
                if(left!=null){
                    queue.add(left);
                }
                if(right!=null){
                    queue.add(right);
                }
            }
            return true;
        }

**解法二：**

**?：回顾一下完全二叉树的定义，除最后一层外，其它层属于全满结构，最后一层的节点全部集中在左侧，因此我们可以分类讨论最后一层节点的情况。**

**情况一：A的左子树是完全二叉树，A的右子树是满二叉树，且左子树高度=右子树高度+1**

![watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5b-r5LmQ55qE5pif55CD_size_20_color_FFFFFF_t_70_g_se_x_16 1][]

**情况二：A的左子树是满二叉树，A的右子树是完全二叉树，且左子树高度=右子树高度+1**

![watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5b-r5LmQ55qE5pif55CD_size_20_color_FFFFFF_t_70_g_se_x_16 2][]

**情况三：A的左子树是满二叉树，A的右子树是完全二叉树，且左子树高度=右子树高度**

**![watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5b-r5LmQ55qE5pif55CD_size_20_color_FFFFFF_t_70_g_se_x_16 3][]**

**情况四：A的左子树是满二叉树，A的右子树是满二叉树，且左子树高度=右子树高度**

![watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5b-r5LmQ55qE5pif55CD_size_20_color_FFFFFF_t_70_g_se_x_16 4][]

### 1.3代码： ###

public static class TreeNode{
            public int val;
            public TreeNode left;
            public TreeNode right;
            public TreeNode(int val){
                this.val=val;
            }
        }
        //完全二叉树的定义：除最后一层之外其它层为全满
        //最后一层为从左到右渐满的结构
        public static class Info{
            public boolean isFBT;
            public boolean isCBT;
            public int height;
            public Info(boolean a,boolean b,int c){
                isFBT=a;
                isCBT=b;
                height=c;
            }
        }
        public static boolean isCBT(TreeNode root ){
            return process(root).isCBT;
        }
        public static Info process(TreeNode node){
            //base case
            if(node==null){
                return new Info(true,true,0);
            }
            Info leftInfo=process(node.left);
            Info rightInfo=process(node.right);
            //高度为左子树高度和右子树高度的较大者+1
            int height=Math.max(leftInfo.height, rightInfo.height)+1;
            //满二叉树的条件:左子树是满二叉树，右子树是满二叉树，左子树高度=右子树高度
            boolean isFBT= leftInfo.isFBT&& rightInfo.isFBT&&leftInfo.height== rightInfo.height;
            boolean isCBT=false;
            if(isFBT){
                isCBT=true;
            }
            else if(leftInfo.isCBT&& rightInfo.isFBT&&(leftInfo.height== rightInfo.height+1)){
                isCBT=true;
            }
            else if(leftInfo.isFBT&& rightInfo.isFBT&&(leftInfo.height== rightInfo.height+1)){
                isCBT=true;
            }
            else if(leftInfo.isFBT&& rightInfo.isCBT&&(leftInfo.height== rightInfo.height)){
                isCBT=true;
            }
            return new Info(isFBT,isCBT,height);
        }

--------------------

## 二：二叉树的最大宽度 ##

> **题目：求二叉树的最大宽度，即节点最多的层的节点数目**

### 2.1：思路 ###

> **?：利用层序遍历，统计每一层的节点数目**

### 2.2: 代码1 ###

//求二叉树所有层中，节点个数最多层的节点数
        //二叉树的bfs的应用 下面写三种解法
        public static class TreeNode{
            public int val;
            public TreeNode left;
            public TreeNode right;
            public TreeNode(int val){
                this.val=val;
            }
        }
        public static int maxWidth(TreeNode root){
            if(root==null){
                return 0;
            }
            Queue<TreeNode> queue=new LinkedList<>();
            queue.add(root);
            //层序遍历会在遍历上一层的时候将下一层逐渐加入队列中
            //这个过程队列中既有上一层节点也有下一层节点
            //当上一层彻底遍历结束的时候，队列中就只有下一层的节点
            int maxWidth=0;
            while(!queue.isEmpty()){
                int size=queue.size();
                maxWidth=Math.max(maxWidth,size);
                for(int i=0;i<size;i++){
                    TreeNode cur=queue.poll();
                    if(cur.left!=null){
                        queue.add(cur.left);
                    }
                    if(cur.right!=null){
                        queue.add(cur.right);
                    }
                }
            }
            return maxWidth;
        }

### 2.2:代码2 ###

**?：我们可以用变量来标记当前层的最后节点，这样我们遍历的时候就能区分每一层。**

//方法二：在统计每一层的时候，刷新每一层的结束位置
        public static int maxWidth2(TreeNode head){
            if(head==null){
                return 0;
            }
            Queue<TreeNode> queue=new LinkedList<>();
            queue.add(head);
            int maxWidth=0;
            TreeNode curEnd=head;//当前层的最后节点
            //在遍历当前层的时候，动态刷新出下一层的最后节点
            //当当前遍历到的节点是当前层的最后节点时，做一次总结
            TreeNode nextEnd=null;
            int curLevelNodes=0;
            while(!queue.isEmpty()){
                TreeNode cur=queue.poll();
                curLevelNodes++;
                if(cur.left!=null){
                    nextEnd=cur.left;
                    queue.add(cur.left);
                }
                if(cur.right!=null){
                    nextEnd=cur.right;
                    queue.add(cur.right);
                }
                //检查一次
                if(cur==curEnd){
                    maxWidth=Math.max(maxWidth,curLevelNodes);
                    curLevelNodes=0;
                    curEnd=nextEnd;
                }
            }
            return maxWidth;
        }

--------------------

## 三：二叉树的最大距离 ##

> **题目：二叉树中任意两节点间都会有一个距离，该距离就是由一个节点到另一个节点的路径上的节点个数。**

### 3.1：思路 ###

> **?：在以x为头的二叉树中，有三种情况**
> 
> **1) 最大距离在x的左子树上**
> 
> **2)最大距离在x的右子树上**
> 
> **3)最大距离经过x节点，是左子树的高度+右子树的高度+1**
> 
> **以x为头整颗树的最大高度是这三种情况的最大值**

### 3.2:代码 ###

public static class TreeNode{
            public int val;
            public TreeNode left;
            public TreeNode right;
            public TreeNode(int val){
                this.val=val;
            }
        }
        public static class Info{
            public int maxDistance;
            public int height;
            public Info(int maxDistance,int height){
                this.maxDistance=maxDistance;
                this.height=height;
            }
        }
        public static Info process(TreeNode node){
            //base case
            if(node==null){
                return new Info(0,0);
            }
            Info leftInfo=process(node.left);
            Info rightInfo=process(node.right);
            int height=Math.max(leftInfo.height,rightInfo.height)+1;
            int maxDistance=Math.max(
                    Math.max(leftInfo.maxDistance, rightInfo.maxDistance),
                    rightInfo.height+ rightInfo.height+1
            );
            return new Info(maxDistance,height);
        }
        public static int maxDistance(TreeNode root){
            return process(root).maxDistance;
        }

--------------------

**由于本人水平十分有限，若有错误请即使告知！如果有帮助别忘了**

**点赞? 收藏✨ 关注✌**

[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5b-r5LmQ55qE5pif55CD_size_20_color_FFFFFF_t_70_g_se_x_16]: https://image.dandelioncloud.cn/pgy_files/images/2024/05/25/0837cf40d5e04153b6c537de217cc6bd.png
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5b-r5LmQ55qE5pif55CD_size_20_color_FFFFFF_t_70_g_se_x_16 1]: https://image.dandelioncloud.cn/pgy_files/images/2024/05/25/736d5bb8b06a477c861a8edc8388d5c1.png
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5b-r5LmQ55qE5pif55CD_size_20_color_FFFFFF_t_70_g_se_x_16 2]: https://image.dandelioncloud.cn/pgy_files/images/2024/05/25/d36300df0c034e48a8105033eb8c4d9e.png
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5b-r5LmQ55qE5pif55CD_size_20_color_FFFFFF_t_70_g_se_x_16 3]: https://image.dandelioncloud.cn/pgy_files/images/2024/05/25/88b8048e986e47f09abeae54c83e7bdb.png
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5b-r5LmQ55qE5pif55CD_size_20_color_FFFFFF_t_70_g_se_x_16 4]: https://image.dandelioncloud.cn/pgy_files/images/2024/05/25/ad1debf5cbc345fc8700ea42e7fa787d.png