《二叉树刷题计划》——相同的树、对称二叉树、另一棵树的子树

一时失言乱红尘 2024-04-23 15:39 99阅读 0赞

**目录**

?相同的树

?对称二叉树

?另一棵树的子树

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

## ?相同的树 ##

![0ecab350e1404f2f9e756343d8dbe4f4.png][]

思路：

> ?如果这两棵树所各自对应的每个结点都相同，那么这两棵树就是相同的树。从根结点开始，然后再递归判断这两棵树各自的左右子树是否相同。**只有当这两棵树的左右子树都相同时，才能说明是相同的树。**

?而判断左右子树是否相同，**又能转换为相应的子问题求解——即左右子树的子树是否相同，就**这样从上到下的进行递归判断，在递归的过程就完成了对每个结点的判断。

代码如下：

>     class Solution {
>         public boolean isSameTree(TreeNode p, TreeNode q) {
>             if (p == null && q != null) return false;
>             if (p != null && q == null) return false;
>             if (p == null && q == null) { // 如果代码能走到这里，说明p、q要么都为空，要么都不为空
>                 return true; // 都为空也认为是相同的
>             }
>             if (p.val != q.val) return false; // 代码走到这里，说明q、q都不为空
>     
>             return isSameTree(p.left, q.left) && isSameTree(p.right, q.right); // 如果两个根结点的左右子结点同时为相同，说明是这两个树是相同的
>         }
>     }

## **?对称二叉树** ##

![025a5364fb844f139d2d61446a399b74.png][]

思路：

这个题目也其实也是判**断树的各自对应结点是否相同**，不过这里要判断的结点是呈轴对称分布的。即**左子树的左子结点和右子树的右子结点要相同**&&**左子树的右子结点和右子树的左子结点要相同。**

代码：

>     class Solution {
>         // 判断两个结点是否轴对称
>         public boolean tmp (TreeNode leftNode, TreeNode rightNode) {
>             if (leftNode != null && rightNode == null) return false;
>             if (leftNode == null && rightNode != null) return false;
>             // 都为空时，也认为相同
>             if (leftNode == null && rightNode == null) return true; // 代码能走到这里，说明这两个结点要么都为空要么都不为空
>             
>             if (leftNode.val != rightNode.val) return false; // 代码能走到这里，说明两个都不为空
>             // 从上到下进行递归，对每个结点都进行了判断
>             return tmp(leftNode.left, rightNode.right) && tmp(leftNode.right, rightNode.left);// 当只有当左子树的左子结点和右子树的右子结点相同 && 左子树的右子节点和右子树的左子节点相同的时候，才是轴对称的
>     
>         }
>         public boolean isSymmetric(TreeNode root) {
>             return tmp(root.left, root.right); // 这一步其实就是判断根结点的左子树和右子树是否轴对称
>         }
>     }

## ?另一棵树的子树 ##

![f9f44bd04b7147028a1c16dffef2f70f.png][]

思路：

要判断一个树 subRoot 是不是树Root的子树，**那么可以判断 subRoot 是否和树 Root 的任意子树相等。**那么就转化成上面的题**——判断两个树是否相同**

首先我们需要先判断root和subRoot是否相同，然后递归判断root的左子树和subRoot是否相同，接着就是root右子树是否相同，只要有一个相同就说明subRoot是root的一个子树。

那如果都不相同呢？那就判断root子树的子树是否和root相同呀！当递归判断到root的子树都为空时，如果还不相同，就说明subRoot真的不是root的子树。

**代码**

>     class Solution {
>         // 判断是否是相同的树
>     public boolean isSameTree(TreeNode p, TreeNode q) {
>             if (p == null && q != null) return false;
>             if (p != null && q == null) return false;
>             if (p == null && q == null) { // 如果代码能走到这里，说明p、q要么都为空，要么都不为空
>                 return true; // 都为空也认为是相同的
>             }
>             if (p.val != q.val) return false; // 代码走到这里，说明q、q都不为空
>     
>             return isSameTree(p.left, q.left) && isSameTree(p.right, q.right); // 如果两个根结点的左右子结点同时为相同，说明是这两个树是相同的
>         }
>     
>         //是不是子树 时间复杂度：O(t * s)
>         public boolean isSubtree(TreeNode root, TreeNode subRoot) {
>             if(root == null) return false; // 当递归到子树root都为空，说明subRoot一定不是root的子树
>             // 判断包括当前结点在内的整个树是否和subRoot相同
>             if(isSameTree(root,subRoot)) return true;
>             // 判断当前树的左子树是否和subRoot相同
>             if(isSubtree(root.left,subRoot)) return true;
>             // 判断当前树的左子树是否和subRoot相同
>             if(isSubtree(root.right,subRoot)) return true;
>     
>             return false; // 如果能走到这里，说明前面三个递归都结束了，如果root从上到下的所有子树没有一个是和subRoot是相同的（如果相同就返回了）,说明subRoot真的不是root的子树
>         }
>     }

[0ecab350e1404f2f9e756343d8dbe4f4.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/0afa8e23721743b996cf776e9116cf0b.png
[025a5364fb844f139d2d61446a399b74.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/136eeb2119bb4f0486532352c7b7ae9f.png
[f9f44bd04b7147028a1c16dffef2f70f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/c3de68bbfeac4ad6b445479fd68aae35.png