Leetcode 572：另一个树的子树

题目描述

给定两个非空二叉树 s 和 t，检验 s 中是否包含和 t 具有相同结构和节点值的子树。s 的一个子树包括 s 的一个节点和这个节点的所有子孙。s 也可以看做它自身的一棵子树。

示例

解题思路

这个题我用两个函数来实现的，首先是官方给的isSubtree()函数，它主要是来做寻找到S和T第一个相同的结点。第二个函数就是isSub()函数，它主要是用来在找到这个结点之后，子树的判断。
它们的思路如下：

isSubtree()函数

s为空，则一定false；

然后判断当前S和T的结点值是否相等（isSub子函数)，若相等，返回true（if语句括号里面收到true的时候，一定是在isSub所有点都比较完成了）；

若当前值不相等，那么分别看s的左子树和s的右子树里面有没有相等的。

isSub()函数

如果当前点都为null，那么这一步是相等的，return true；

如果当前点一个有值，一个为空，那么一定是false（两个点都为空的情况在上面已经返回了，所以这里肯定没有）；

如果当前点两个值不相等，那么没必要比较下去了，直接return false；

如果当前点的两个值相等，那么分别比较左子树和右子树。

代码实现

bool isSub(TreeNode* s, TreeNode* t)
{
    if (!s && !t)
        return true;
    if (!s || !t)
        return false;
    if (s->val != t->val)
        return false;
    return isSub(s->left, t->left) && isSub(s->right, t->right);
}
bool isSubtree(TreeNode* s, TreeNode* t) {
    if (!s)
        return false;
    if (isSub(s, t))
        return true;
    return isSubtree(s->left, t) || isSubtree(s->right, t);
}

Leetcode 581：最短无序连续子数组

题目描述

给定一个整数数组，你需要寻找一个连续的子数组，如果对这个子数组进行升序排序，那么整个数组都会变为升序排序。你找到的子数组应是最短的，请输出它的长度。

示例

示例1
输入: [2, 6, 4, 8, 10, 9, 15]
输出: 5
解释: 你只需要对 [6, 4, 8, 10, 9] 进行升序排序，那么整个表都会变为升序排序。

解题思路

我的思路很简单，对整个数组进行排序，然后图方便，将所有与原来相同位置上数字不同的位置记录下来，然后记录start为第一个位置，end为最后一个位置，结果就是end-start-1。当然也可以用其它方法只记录end和start，节省空间。

之所以这样做是因为，找到的子数组是最短的，说明应该找的是第一个动的位置和最后一个动的位置及包含它们在内的子数组，所以才这样做。

代码实现

int findUnsortedSubarray(vector<int>& nums) {
    vector<int>tmp(nums);
    sort(nums.begin(), nums.end());
    vector<int>pos;
    for (int i = 0; i < nums.size(); i++)
    {
        if (nums[i] != tmp[i])
        {
            pos.push_back(i);
        }
    }
    int posize = pos.size();
    if(posize==0)
        return 0;
    int start = pos[0];
    int end = pos[pos.size() - 1];
    //cout << "start=" << start << "end=" << end << endl;
    return (end - start + 1);
}