二叉树重点突破

àì夳堔傛蜴生んèń 2023-09-27 11:54 23阅读 0赞

![在这里插入图片描述][8a0773bd39c844f9a81a23e8baafd092.gif_pic_center]

>  个人主页：[熬夜磕代码丶][Link 1]  
>  作品专栏: [数据结构与算法][Link 2]  
>  我变秃了，也变强了  
> 最近接触到一个很好用的软件:Apifox Apifox = Postman + Swagger + Mock + JMeter  
> 点我进入[Apifox][]

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

*  一、两个数是否相同
 *  二、另一棵树的子树
 *  三、二叉树的最大深度
 *  四、平衡二叉树
 *  五、对称二叉树

## 一、两个数是否相同 ##

给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。  
如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。  
![在这里插入图片描述][3e2e587ce4dd4473bd9ebde1def35044.png]  
![在这里插入图片描述][3176e3130fef455d90747fd4bd981db8.png]  
**基本思路：**  
对二叉树进行遍历，判断每一个结点的结构和数值是否相同，不同直接返回false，否则继续判断左子树和右子树直到二叉树遍历完成为止。  
![在这里插入图片描述][99729f7355734d20b724338e0d94434a.png]

public boolean isSameTree(TreeNode p, TreeNode q) {
        
            //相同的树
            if(p == null && q != null || p != null && q == null) {
        
                return false;
            }
            if(p == null && q == null) {
        
                return true;
            }
            if(p.val != q.val) {
        
                return false;
            }
            return isSameTree(p.left,q.left) && isSameTree(p.right,q.right);
        }

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

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

![在这里插入图片描述][368675446c4549ba8d3b6cd4cc0f7a31.png]  
**基本思路：**  
遍历root每一个结点去和子树subRoot去判断是否为相同的树，如果相同返回true，否则继续遍历，如果遍历结束还没有找到，那就返回false,这里可以复用上一题相同树的代码。

public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        
            if(root == null || subRoot == null) {
        
                return false;
            }
            if(isSameTree(root,subRoot)) {
        
                return true;
            }
            boolean flg1 = isSubtree(root.left,subRoot);
            if(flg1 == true) {
        
                return true;
            }
            boolean flg2 = isSubtree(root.right,subRoot);
            if(flg2 == true) {
        
                return true;
            }
            return false;
        }
        public boolean isSameTree(TreeNode p, TreeNode q) {
        
            //相同的树
            if(p == null && q != null || p != null && q == null) {
        
                return false;
            }
            if(p == null && q == null) {
        
                return true;
            }
            if(p.val != q.val) {
        
                return false;
            }
            return isSameTree(p.left,q.left) && isSameTree(p.right,q.right);
        }

## 三、二叉树的最大深度 ##

给定一个二叉树，找出其最大深度。  
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。  
![在这里插入图片描述][fd85e5a3a1cd4e959d708d899b41f528.png]  
**解题思路：**  
这里我们采用子问题方法，将二叉树的最大深度分解为左子树的最大深度和右子树最大深度的最大值+1即为本二叉树的最大深度。

public int maxDepth(TreeNode root) {
        
            if(root == null) {
        
                return 0;
            }
            if(root.left == null && root.right == null) {
        
                return 1;
            }
            int leftMax = maxDepth(root.left);
            int rightMax = maxDepth(root.right);
            return leftMax > rightMax ? leftMax + 1 : rightMax + 1;
        }

## 四、平衡二叉树 ##

给定一个二叉树，判断它是否是高度平衡的二叉树。  
本题中，一棵高度平衡二叉树定义为： 一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。  
![在这里插入图片描述][091f2d9cac9941b1b0f14aed9bd25101.png]  
![在这里插入图片描述][67b850d18575436687112cb51b797695.png]  
**基本思路：**  
遍历二叉树，去判断二叉树每个结点的左右子树的高度差，如果小于2那么在判断左子树和右子树，如果有任何一个结点不满足，那么就不是平衡二叉树，如果每一个结点都满足那么就是平衡二叉树。

public boolean isBalanced(TreeNode root) {
        
            if(root == null) {
        
                return true;
            }
            int left = maxDepth(root.left);
            int right = maxDepth(root.right);
            return Math.abs(left - right) <  2 && isBalanced(root.left) && isBalanced(root.right);
        }
        public int maxDepth(TreeNode root) {
        
            if(root == null) {
        
                return 0;
            }
            if(root.left == null && root.right == null) {
        
                return 1;
            }
            int leftMax = maxDepth(root.left);
            int rightMax = maxDepth(root.right);
            return leftMax > rightMax ? leftMax + 1 : rightMax + 1;
        }

这样显然可以达到目的，但是时间复杂度达到了O(n²),能不能O(n)就完成目标呢？  
![在这里插入图片描述][3056b55ad3c946b6bfa3c8e1b49141c5.png]  
我们对每个结点进行左子树和右子树高度进行计算，如果左右子树的高度差大于1那么直接返回-1，否则继续计算结点的高度。

public boolean isBalanced(TreeNode root) {
        
            if(root == null){
        
                return true;
            }
            return maxDepth1(root) > 0;
        }
        public int maxDepth1(TreeNode root) {
        
            if(root == null) {
        
                return 0;
            }
            if(root.left == null && root.right == null) {
        
                return 1;
            }
            int leftMax = maxDepth1(root.left);
            int rightMax = maxDepth1(root.right);
            if(leftMax < 0 || rightMax < 0 || Math.abs(leftMax - rightMax) >1 ) {
        
                return -1;
            }else {
        
                return Math.max(leftMax,rightMax) + 1;
            }
        }

## 五、对称二叉树 ##

给你一个二叉树的根节点 root ， 检查它是否轴对称。  
![在这里插入图片描述][defc71ab50a04a02a02d302c6ec9ff7a.png]  
![在这里插入图片描述][7175e87d4b2c42fd9cf480d683a70e28.png]  
**基本思路：**  
二叉树是否对称分解为左子树和右子树是否对称相等，然后在左子树的左节点和右子树的右节点，左子树的右节点和右子树的左节点是否相等。

public boolean isSymmetric(TreeNode root) {
        
            if(root == null) {
        
                return true;
            }
            return isSame(root.left,root.right);
        }
        public boolean isSame(TreeNode left,TreeNode right) {
        
            if(left == null && right != null || left != null && right == null) {
        
                return false;
            }
            if(left == null && right == null) {
        
                return true;
            }
            if(left.val != right.val) {
        
                return false;
            }
            return isSame(left.left,right.right) && isSame(left.right,right.left);
        }

[8a0773bd39c844f9a81a23e8baafd092.gif_pic_center]: https://img-blog.csdnimg.cn/8a0773bd39c844f9a81a23e8baafd092.gif#pic_center
[Link 1]: https://blog.csdn.net/buhuisuanfa?spm=1018.2226.3001.5343
[Link 2]: https://blog.csdn.net/buhuisuanfa/category_11999355.html?spm=1001.2014.3001.5482
[Apifox]: http://apifox.cn/a103aoye
[3e2e587ce4dd4473bd9ebde1def35044.png]: https://img-blog.csdnimg.cn/3e2e587ce4dd4473bd9ebde1def35044.png
[3176e3130fef455d90747fd4bd981db8.png]: https://img-blog.csdnimg.cn/3176e3130fef455d90747fd4bd981db8.png
[99729f7355734d20b724338e0d94434a.png]: https://img-blog.csdnimg.cn/99729f7355734d20b724338e0d94434a.png
[368675446c4549ba8d3b6cd4cc0f7a31.png]: https://img-blog.csdnimg.cn/368675446c4549ba8d3b6cd4cc0f7a31.png
[fd85e5a3a1cd4e959d708d899b41f528.png]: https://img-blog.csdnimg.cn/fd85e5a3a1cd4e959d708d899b41f528.png
[091f2d9cac9941b1b0f14aed9bd25101.png]: https://img-blog.csdnimg.cn/091f2d9cac9941b1b0f14aed9bd25101.png
[67b850d18575436687112cb51b797695.png]: https://img-blog.csdnimg.cn/67b850d18575436687112cb51b797695.png
[3056b55ad3c946b6bfa3c8e1b49141c5.png]: https://img-blog.csdnimg.cn/3056b55ad3c946b6bfa3c8e1b49141c5.png
[defc71ab50a04a02a02d302c6ec9ff7a.png]: https://img-blog.csdnimg.cn/defc71ab50a04a02a02d302c6ec9ff7a.png
[7175e87d4b2c42fd9cf480d683a70e28.png]: https://img-blog.csdnimg.cn/7175e87d4b2c42fd9cf480d683a70e28.png