🤞目录🤞
【大家好，我是爱干饭的猿，如果喜欢这篇文章，点个赞👍，关注一下吧，后续会一直分享题目与算法思路】
🥎1. 数的子结构
描述
输入两棵二叉树A，B，判断B是不是A的子结构。（我们约定空树不是任意一个树的子结构）
例：
假如给定A为{8,8,7,9,2,#,#,#,#,4,7}，B为{8,9,2}，2个树的结构如下，可以看出B是A的子结构
解题思路：
🎈二叉树一般是递归定义的，所以递归做法比较常见。
子结构可以理解为是原树的子树，此题来看，B树是A树的子树。也就是说，B的根节点+左子树+右子树 都可以在A树中找到。
所以，我们先确定子树根节点在原树中的位置，然后判断其后续的左右子树是否相同。
?👓代码如下：
public boolean isSubtree(TreeNode root,TreeNode subRoot) {
if(root == null && subRoot == null){
return true;
}
if(root == null || subRoot ==null){
return false;
}
return isSameTree(root,subRoot) ||
isSubtree(root.left,subRoot) || isSubtree(root.right,subRoot);
}
//与（leetcode 100.相同的树） 有相似之处，
// 但是此处当子链为空时，主链不一定为空
public boolean isSameTree(TreeNode p, TreeNode q) {
// 如果q为空说明子链已将比较完了，且都相等
if(q == null){
return true;
}
// 走到这，说明q子链不为空，p为空，表示q并不是p的子链
if(p == null){
return false;
}
return p.val==q.val && isSameTree(p.left,q.left) &&isSameTree(p.right,q.right);
}🥎2.?二叉树的镜像
描述
操作给定的二叉树，将其变换为源二叉树的镜像。
例：
原二叉树
?其镜像二叉树
解题思路：
🎈还是用递归的思路。我们发现，二叉树的镜像，是不断遍历根节点，并交换左右子树位置。
所以我们可以用递归先序遍历（根 左 右）来实现左右子树的交换。
👓代码如下：
public TreeNode Mirror (TreeNode pRoot) {
if(pRoot == null){
return null;
}
// 交换当前pRoot 的左右子树
TreeNode temp = pRoot.left;
pRoot.left = pRoot.right;
pRoot.right = temp;
// 处理pRoot的左子树
Mirror(pRoot.left);
// 处理pRoot的右子树
Mirror(pRoot.right);
return pRoot;
}🥎3.?删除链表中重复的结点
描述
在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。
例如，链表 1->2->3->3->4->4->5? 处理后为 1->2->5
??
解题思路：
🎈首先，我们知道该链表是非减链表，我们可以先定义一个虚拟头结点dummyHead，先将链表接于虚拟头节点之后，然后定义快慢指针，慢指针（pre）先指向头结点，快指针(last)指向链表头结点，比较last.val 与 last.next.val 是否相同，先找到重复节点，然后使last = last.next，继续比较last.val 与 last.next.val 是否相同，找到重复节点的末位置，删除节点时，只需要将 pre.next = last.next 即可。返回时，只需返回dummyHead.next 即可。
👓代码如下：?
public ListNode deleteDuplication(ListNode pHead) {
if(pHead == null){
return null;
}
// 定义一个虚拟头结点
ListNode dummyNode = new ListNode(-1);
dummyNode.next = pHead;
// 定义快慢指针
ListNode pre = dummyNode;
ListNode last = pre.next;
while(last != null){
// 找到重复节点
while(last.next != null && last.val != last.next.val){
pre = pre.next;
last = last.next;
}
// 找到重复节点的末位置
while(last.next != null && last.val == last.next.val){
last =last.next;
}
// 三种结果
// 1. last == null, prev.next == last 没有相同值的节点
// 2. last == null, prev.next != last 最后一个节点也是重复节点，需去重
// 3. last != null, prev.next != last 找到了其中一个一个相同值节点的末位置，需去重
// 有重复节点，需去重
if(pre.next != last){
pre.next = last.next;
}
last = last.next;
}
return dummyNode.next;
}?
