【每日练习】二叉树

客官°小女子只卖身不卖艺 2024-04-23 21:21 61阅读 0赞

> ⭐ 作者：小胡\_不糊涂  
> ? 作者主页：[小胡\_不糊涂的个人主页][Link 1]  
> ? 收录专栏：[二叉树][Link 2]  
> ? 持续更文，关注博主少走弯路，谢谢大家支持 ?

#### 文章目录 ####

*  一、100. 相同的树
 *   *  1. 题目简介
     *  2. 代码
     *  3. 运行结果
 *  二、572. 另一棵树的子树
 *   *  1. 题目简介
     *  2. 代码
     *  3. 运行结果
 *  三、226. 翻转二叉树
 *   *  1. 题目简介
     *  2. 代码
     *  3. 运行结果
 *  四、110平衡二叉树
 *   *  1.题目介绍
     *  2. 代码
     *  3. 运行结果

## 一、100. 相同的树 ##

### 1. 题目简介 ###

> 给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。  
> 如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。  
> ![在这里插入图片描述][07913b2b09464e9484c9150efc65a6f7.png]

### 2. 代码 ###

class Solution {
        
        public boolean isSameTree(TreeNode p, TreeNode q) {
        
            if(p==null&&q==null){
        
                return true;//都为空
            }else if(p==null || q==null){
        
                return false;//一个为空
            }else if(p.val!=q.val){
        
                return false;//根节点是否相同
            }else{
        
                return isSameTree(p.left,q.left)&&isSameTree(p.right,q.right);//比较左右节点是否相同
            }
    
        }
    }

### 3. 运行结果 ###

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

## 二、572. 另一棵树的子树 ##

### 1. 题目简介 ###

> 给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在，返回 true ；否则，返回 false 。  
> 二叉树 tree 的一棵子树包括 tree 的某个节点和这个节点的所有后代节点。tree 也可以看做它自身的一棵子树。

### 2. 代码 ###

class Solution {
        
        public boolean isSubtree(TreeNode r, TreeNode s) {
        
            if(s==null) return true;
            if(r==null) return false;
            return isSubtree(r.left,s)||isSubtree(r.right,s)||isSameTree(r,s);
        }
        public boolean isSameTree(TreeNode p,TreeNode q){
        
            if(p==null&&q==null){
        
                return true;
            }else if(p==null || q==null){
        
                return false;
            }else if(p.val!=q.val){
        
                return false;
            }else{
        
                return isSameTree(p.left,q.left)&&isSameTree(p.right,q.right);
            }
        }
    }

### 3. 运行结果 ###

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

## 三、226. 翻转二叉树 ##

### 1. 题目简介 ###

> 给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点  
> ![在这里插入图片描述][f4e47afcc06d42fbb581fbe88fda973e.png]

### 2. 代码 ###

class Solution {
        
        //翻转二叉树
        public TreeNode invertTree(TreeNode root) {
        
            if(root==null){
        
                return null;
            }
            TreeNode tmp=root.left;
            root.left=root.right;
            root.right=tmp;
    
            invertTree(root.left);
            invertTree(root.right);
    
            return root;
        }
    }

### 3. 运行结果 ###

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

## 四、110平衡二叉树 ##

### 1.题目介绍 ###

> 给定一个二叉树，判断它是否是 平衡二叉树（平衡二叉树 是指该树所有节点的左右子树的深度相差不超过 1）  
> ![在这里插入图片描述][b89ea7920fa540aca2e283ab16b8d801.png]

### 2. 代码 ###

class Solution {
        
        //平衡二叉树
        public boolean isBalanced(TreeNode root) {
        
            if(root==null){
        
                return true;
            }else{
        
                return Math.abs(height(root.left)-height(root.right))<=1&&isBalanced(root.left)&&isBalanced(root.right);
            }
        }
        public int height(TreeNode r){
        
            if(r==null){
        
                return 0;
            }else{
        
                return Math.max(height(r.left),height(r.right))+1;
            }
        }
    }

### 3. 运行结果 ###

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

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

来源：力扣（LeetCode），著作归力扣网络所有。  
如果本篇文章对你有所启发的话，希望可以多多支持作者，谢谢大家！

[Link 1]: https://blog.csdn.net/iLoyo_
[Link 2]: http://t.csdnimg.cn/wrQhX
[07913b2b09464e9484c9150efc65a6f7.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/cd6a8ab55a8b41bfb181e3c7bf3e0ba6.png
[e4133c759d384f6fa974f6baf077ba64.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/1919ff902464418eadf35c3aaa0cbe46.png
[e66976c6d5994eb3ad334e8a25d2fb6e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/95e861d9801f489882f8ece7d6df4eca.png
[f4e47afcc06d42fbb581fbe88fda973e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/0b8b98972fad464e82855bb205d20238.png
[541718f0142549aa8b048e00a1a6ff1b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/2836f47e1c1d409994d4ef0932c9dbd3.png
[b89ea7920fa540aca2e283ab16b8d801.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/d37ece2e300c4f71a63f6bd0a4c60245.png
[8b6b3e7dcab147e8bf2730a80e1a1685.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/fa303abe275a4af3afc1ee4e2bc3dca4.png