剑指offer经典题目整理（四）

一、树的子结构

1.链接

树的子结构_牛客题霸_牛客网 (nowcoder.com)

2.描述

给两颗二叉树A B，判断B是不是A的子结构

3.思路

将问题拆解开来，首先是找到a树中子结构的位置，然后是判断是否相同，也就是说，我们需要去遍历一边a树，逐一把每个节点作为根去和b的根进行判断是否相同，如果相同，则说明确实是子结构，此外，题目还要求，空树不属于任何树的子结构

4.参考代码

ps:一开始理解错了子结构的意思，理解成子树了，所以判断是否子结构的函数名字写的是is_same

class Solution 
{
public:
	bool is_same(TreeNode* A, TreeNode* B)
	{
		if(B == nullptr)
		{
			return true;
		}
		if(A == nullptr)
		{
			return false;
		}
		if(A->val != B->val)
		{
			return false;
		}
		return is_same(A->left, B->left) && is_same(A->right, B->right);
	}

    bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2) 
	{
		if(pRoot1 == nullptr || pRoot2 == nullptr)
		{
			return false;
		}
		bool ret = is_same(pRoot1, pRoot2);
		if(ret)
		{
			return true;
		}
		else
		{
			return HasSubtree(pRoot1->left, pRoot2) || HasSubtree(pRoot1->right,pRoot2);
		}
    }
};

二、二叉树的镜像

1.链接

二叉树的镜像_牛客题霸_牛客网 (nowcoder.com)

2.描述

操作给定的二叉树，将其变换为源二叉树的镜像。

3.思路

通过观察发现，镜像后就是原二叉树每个节点的左右子树交换，因此很容易想到，用递归的方法遍历每个节点，然后去将每个节点的左右子树交换，遇到空则返回

4.参考代码

class Solution {
public:

    TreeNode* Mirror(TreeNode* pRoot) 
    {
        if(pRoot == nullptr)
        {
            return nullptr;
        }
        TreeNode* tmp = pRoot->left;
        pRoot->left = pRoot->right;
        pRoot->right = tmp;
        Mirror(pRoot->left);
        Mirror(pRoot->right);
        return pRoot;
    }
};

三、删除链表重复节点

1.链接

删除链表中重复的结点_牛客题霸_牛客网 (nowcoder.com)

2.描述

给一个单链表，要求删掉所有重复的区间，一个不留，然后返回

3.思路

4.参考代码

class Solution {
public:
    ListNode* deleteDuplication(ListNode* pHead) 
    {
        if(pHead == nullptr)
        {
            return nullptr;
        }

        ListNode* newhead = new ListNode(0);
        newhead->next = pHead;
        ListNode* fast = pHead;
        ListNode* slow = newhead;

        while(fast)
        {
            while(fast->next && fast->val != fast->next->val)
            {
                fast = fast->next;
                slow = slow->next;
            }
            while(fast->next && fast->val == fast->next->val)
            {
                fast = fast->next;
            }
            if(slow->next != fast)
            {
                slow->next = fast->next;
            }
            fast = fast->next;
        }
        ListNode* ret = newhead->next;
        delete newhead;
        return ret;
    }
};