【leetcode】相同的树、另一棵树的子树、翻转二叉树（利用深度优先遍历）

Hi~！这里是奋斗的明志，很荣幸您能阅读我的文章，诚请评论指点，欢迎欢迎 ~~
🌱🌱个人主页：奋斗的明志
🌱🌱所属专栏：数据结构、LeetCode专栏

📚本系列文章为个人学习笔记，在这里撰写成文一为巩固知识，二为展示我的学习过程及理解。文笔、排版拙劣，望见谅。

前言

一定要结合图像来写题，递归有点绕

一、相同的树

100.相同的树

1. 题目

2. 解析

• 一个为空，一个不为空，说明不是两棵相同的树
• 如果两个都为空，说明是相同的树
• 两个都不为空，但是值不一样，说明不是两棵相同的树

isSameTree 方法解释：

• 参数：方法接收两个 TreeNode 类型的参数 p 和 q，分别代表两棵二叉树的根节点。
  返回值：返回一个布尔值，表示两棵树是否相同。

• 逻辑：
  首先，通过判断根节点的情况来确定树的结构是否相同：
  如果 p 为 null 而 q 不为 null，或者 p 不为 null 而 q 为 null，则树的结构不同，返回 false。
  如果两个根节点都为 null，说明两棵树为空树，返回 true。
  如果根节点的值 p.val 不等于 q.val，则根节点的值不同，返回 false。
  如果根节点的值相同，则递归地比较它们的左子树和右子树，判断左右子树是否相同。

递归调用：

• isSameTree(p.left, q.left) 递归地比较两棵树的左子树。
• isSameTree(p.right, q.right) 递归地比较两棵树的右子树。
• 最终，通过递归的方式，判断了整棵树的结构和节点值是否完全相同。

这段代码利用递归的思想，深度优先地比较了两棵二叉树的结构和节点值，判断它们是否相同。

3. 完整代码

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public boolean isSameTree(TreeNode p, TreeNode q) {//首先判断根节点if((p == null && q != null) || (p != null && q == null)){//结构不一样return false;} //如果上面if语句没有走 说明 剩下两个都为空 或者 两个都不为空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);}
}

二、另一棵树的子树

写这一道题，要深入理解第一道题，因为要用到

527.另一棵树的子树

1. 题目

2. 解析（深度优先搜索暴力匹配）

• 从根节点开始判断，如果主树为空的话，则不可能包含子树

【isSubtree方法】

3. 完整代码

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public boolean isSubtree(TreeNode root, TreeNode subRoot) {if(root == null){return false;}if(isSametree(root,subRoot)){return true;}if(isSubtree(root.left,subRoot)){return true;}if(isSubtree(root.right,subRoot)){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);}
}

4.深度优先搜索序列上做串匹配

class Solution {List<Integer> sOrder = new ArrayList<Integer>();List<Integer> tOrder = new ArrayList<Integer>();int maxElement, lNull, rNull;public boolean isSubtree(TreeNode s, TreeNode t) {maxElement = Integer.MIN_VALUE;getMaxElement(s);getMaxElement(t);lNull = maxElement + 1;rNull = maxElement + 2;getDfsOrder(s, sOrder);getDfsOrder(t, tOrder);return kmp();}public void getMaxElement(TreeNode t) {if (t == null) {return;}maxElement = Math.max(maxElement, t.val);getMaxElement(t.left);getMaxElement(t.right);}public void getDfsOrder(TreeNode t, List<Integer> tar) {if (t == null) {return;}tar.add(t.val);if (t.left != null) {getDfsOrder(t.left, tar);} else {tar.add(lNull);}if (t.right != null) {getDfsOrder(t.right, tar);} else {tar.add(rNull);}}public boolean kmp() {int sLen = sOrder.size(), tLen = tOrder.size();int[] fail = new int[tOrder.size()];Arrays.fill(fail, -1);for (int i = 1, j = -1; i < tLen; ++i) {while (j != -1 && !(tOrder.get(i).equals(tOrder.get(j + 1)))) {j = fail[j];}if (tOrder.get(i).equals(tOrder.get(j + 1))) {++j;}fail[i] = j;}for (int i = 0, j = -1; i < sLen; ++i) {while (j != -1 && !(sOrder.get(i).equals(tOrder.get(j + 1)))) {j = fail[j];}if (sOrder.get(i).equals(tOrder.get(j + 1))) {++j;}if (j == tLen - 1) {return true;}}return false;}
}

三、翻转二叉树

226.翻转二叉树

1.题目

2.解析（利用深度优先搜索）

• 首先要进行空树检查
• 进行单节点树检查
• 翻转操作：首先创建一个临时节点 tmp，将 root 的左右子树交换。这里直接交换了节点的引用，而不是交换节点的值。
• 递归地对 root 的左子树和右子树进行翻转操作。
• 返回经过翻转处理后的根节点 root

3.完整代码

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public TreeNode invertTree(TreeNode root) {//空树if(root == null){return null;}//只有一个节点的树if(root.left == null && root.right == null && root.val >= -100 && root.val <= 100){return root;}//定义一个中间结点TreeNode tmp = new TreeNode();tmp.left = root.left;tmp.right = root.right;root.left = tmp.right;root.right = tmp.left;invertTree(root.left);invertTree(root.right);return root;}
}

【改进后的代码】

class Solution {public TreeNode invertTree(TreeNode root) {if (root == null) {return null;}// 交换左右子树TreeNode left = invertTree(root.left);TreeNode right = invertTree(root.right);root.left = right;root.right = left;return root;}
}

这个简化版本避免了使用额外的临时节点，并且更加清晰地表达了翻转操作

四、总结

将大问题划分成一个一个相同的小问题来求解，一定要注意判断条件