绵阳市建设工程质监站网站,wordpress 中文tag,英国免费做网站,手机网站建设网站Hi~#xff01;这里是奋斗的明志#xff0c;很荣幸您能阅读我的文章#xff0c;诚请评论指点#xff0c;欢迎欢迎 ~~ #x1f331;#x1f331;个人主页#xff1a;奋斗的明志 #x1f331;#x1f331;所属专栏#xff1a;数据结构、LeetCode专栏 #x1f4da;本系… Hi~这里是奋斗的明志很荣幸您能阅读我的文章诚请评论指点欢迎欢迎 ~~ 个人主页奋斗的明志 所属专栏数据结构、LeetCode专栏 本系列文章为个人学习笔记在这里撰写成文一为巩固知识二为展示我的学习过程及理解。文笔、排版拙劣望见谅。 链表面试题 前言一、相同的树1. 题目2. 解析3. 完整代码 二、另一棵树的子树1. 题目2. 解析深度优先搜索暴力匹配3. 完整代码4.深度优先搜索序列上做串匹配 三、翻转二叉树1.题目2.解析利用深度优先搜索3.完整代码 四、总结 前言 一定要结合图像来写题递归有点绕 一、相同的树
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 {ListInteger sOrder new ArrayListInteger();ListInteger tOrder new ArrayListInteger();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, ListInteger 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;}
}这个简化版本避免了使用额外的临时节点并且更加清晰地表达了翻转操作 四、总结 将大问题划分成一个一个相同的小问题来求解一定要注意判断条件
