🤞目录🤞
【大家好，我是爱干饭的猿，如果喜欢这篇文章，点个赞👍，关注一下吧，后续会一直分享题目与算法思路】
🥎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; }
