剑指offer21-25

第21题：输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。

思路：先将压栈序列压入辅助栈s中，当辅助栈顶元素和出栈序列有相同时，出栈，然后继续检测，直到辅助栈没有元素为止。无元素为true，有元素为false

class Solution {
public:
    bool IsPopOrder(vector<int> pushV,vector<int> popV) {
        if(pushV.size() == 0 || popV.size() == 0)
            return false;
        stack<int> s;
        for(int i = 0, j = 0; i < pushV.size(); ++i)
        {
            s.push(pushV[i]);
            while(j < popV.size() && s.top() == popV[j])
            {
                s.pop();
                j++;
            }
        }
        return s.empty();
    }
};

第22题：从上往下打印出二叉树的每个节点，同层节点从左至右打印

思路：

循环：就是二叉树的层序遍历，使用队列实现最为方便，先让根节点入队列，在让左子树和右子树分别入队列即可。q.pop()很关键。

//循环
class Solution {
public:
    vector<int> PrintFromTopToBottom(TreeNode* root) {
        vector<int> res;
        if(root == nullptr)
            return res;
        queue<TreeNode*> q;
        q.push(root);
        while(!q.empty())
        {
            res.push_back(q.front()->val);
            if(q.front()->left)
                q.push(q.front()->left);
            if(q.front()->right)
                q.push(q.front()->right);
            q.pop();
        }
        return res;
    }
};
//递归
//但是内存会超限，一般还是用循环写比较好
class Solution {
public:
    vector<int> PrintFromTopToBottom(TreeNode* root) {
        vector<int> res;
        if(root == nullptr)
            return res;
        queue<TreeNode*> q;
        TreeNode* p = root;
        q.push(root);
        res.push_back(q.front()->val);
        while(p->left || p->right)
        {
        if(p->left)
            q.push(p->left);
        if(p->right)
            q.push(p->right);
        q.pop();
        }
        if(p->left)
            PrintFromTopToBottom(p->left);
        if(p->right)
            PrintFromTopToBottom(p->right);
        return res;
    }
};

第23题：输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。

思路：二叉搜索树的特征:左子树 < 根 < 右子树

//二叉搜索树的后序遍历序列
//递归
class Solution {
public:
    bool VerifySquenceOfBST(vector<int> sequence) {
        if(sequence.size() == 0)
            return false;
        vector<int> leftTree, rightTree;
        int len = sequence.size();
        int root = sequence[len-1];
        int i = 0;
        for(; i < len-1; ++i)
        {
            if(sequence[i] > root)
                break;
        }
        for(int j = i; j < len-1; ++j)
        {
            if(sequence[j] < root)
                return false;
        }
        if(i != 0)
        {
            for(int m = 0; m < i; ++m)
            {
                leftTree.push_back(sequence[m]);
            }
        }
        if(i != len-2)
        {
            for(int n = i; n < len-1; ++n)
            {
                rightTree.push_back(sequence[n]);
            }
        }
        bool left = true, right = true;
        if(leftTree.size() > 1)
            VerifySquenceOfBST(leftTree);
        if(rightTree.size() > 1)
            VerifySquenceOfBST(rightTree);
        return left && right;
    }
};
//循环
class Solution {
public:
    bool VerifySquenceOfBST(vector<int> sequence) {
        size_t size = sequence.size();
        if(size == 0)
            return false;
        int i = 0;
		//size--和之后的i=0相对应，size一直--，就能让循环的终点位置改变，则大循环里面的第二个循环，正好可以再一次判断数列中是否有一部分时满足条件的
        while(size--)
        {
            while(sequence[i] < sequence[size])
                i++;
            while(sequence[i] > sequence[size])
                i++;
            if(i < size)
                return false;
				//当第一次循环时发现，长数列不是我们需要的，此时需要继续判断，其中的部分是不是我们需要的，需要让i从0重新开始增长。
            i = 0;
        }
        return true;
    }
};

第24题：输入一颗二叉树的跟节点和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。(注意: 在返回值的list中，数组长度大的数组靠前)

//二叉树中和为某一值的路径
class Solution {
public:
    vector<vector<int>> res;
    vector<int> path;
    void find(TreeNode* p, int sum)
    {
        if(p == nullptr)
            return;
        path.push_back(p->val);
        if(p->left == nullptr && p->right == nullptr && sum == p->val)
            res.push_back(path);
        else{
            if(p->left)
                find(p->left, sum - p->val);
            if(p->right)
                find(p->right, sum - p->val);
        }
        path.pop_back();
    }
    vector<vector<int> > FindPath(TreeNode* root,int expectNumber) {
        find(root, expectNumber);
        return res;
    }
};

第25题：输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点），返回结果为复制后复杂链表的head。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）

//复杂链表的复制
class Solution {
public:
    RandomListNode* Clone(RandomListNode* pHead)
    {
        if(pHead == nullptr)
            return nullptr;
        RandomListNode* curNode = pHead;
        while(curNode)
        {
            RandomListNode* node = new RandomListNode(curNode->label);
            node->next = curNode->next;
            curNode->next = node;
            curNode = node->next;
        }
        curNode = pHead;
        while(curNode)
        {
            RandomListNode* node = curNode->next;
            if(curNode->random)
            {
                node->random = curNode->random->next;
            }
            curNode = node->next;
        }
        RandomListNode* pCloneHead = pHead->next;
        curNode = pHead;
        RandomListNode* tmp;
        while(curNode->next)
        {
            tmp = curNode->next;
            curNode->next = tmp->next;
            curNode = tmp;
        }
        return pCloneHead;
    }
};