【迎战蓝桥】 算法·每日一题（今日详解）-- day4

🤞目录🤞

💖1. 数的子结构

💖2. 二叉树的镜像

💖3. 删除链表中重复的结点

【大家好，我是爱干饭的猿，如果喜欢这篇文章，点个赞👍，关注一下吧，后续会一直分享题目与算法思路】

🥎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;
    }