剑指offer.C++.code16-20

16. 合并两个排序的链表

• 输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。

// 递归实现
/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
            val(x), next(NULL) {
    }
};*/
class Solution {
public:
    ListNode* Merge(ListNode* pHead1, ListNode* pHead2)
    {
        if (pHead1 == NULL) {
            return pHead2;
        } else if (pHead2 == NULL) {
            return pHead1;
        }
        
        ListNode* pMerge = NULL;
        if (pHead1->val < pHead2->val) {
            pMerge = pHead1;
            pMerge->next = Merge(pHead1->next, pHead2);
        } else {
            pMerge = pHead2;
            pMerge->next = Merge(pHead1, pHead2->next);
        }
        return pMerge;
    }
};

17. 树的子结构

• 输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};*/
// 递归实现，二叉树
class Solution {
public:
    bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2)
    {
        bool res = false;
        if (pRoot1 != NULL && pRoot2 != NULL) {// pRoo2 == NULL 空树
            if (pRoot1->val == pRoot2->val) {
                res = DoesTree1hasTree2(pRoot1, pRoot2);
            }
            if (!res) {
                res = DoesTree1hasTree2(pRoot1->left, pRoot2);
            }
            if (!res) {
                res = DoesTree1hasTree2(pRoot1->right, pRoot2);
            }
        }
        return res;
    }
    
    bool DoesTree1hasTree2(TreeNode* pRoot1, TreeNode* pRoot2) {
        if (pRoot2 == NULL) {// tree2完全重合
            return true;
        }
        if (pRoot1 == NULL) {// tree1先结束
            return false;
        }
        if (pRoot1->val != pRoot2->val) {
            return false;
        }
        return DoesTree1hasTree2(pRoot1->left, pRoot2->left) &&
            DoesTree1hasTree2(pRoot1->right, pRoot2->right);
        
    }
};

18. 二叉树的镜像

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

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};*/
// 递归实现，二叉树
class Solution {
public:
    void Mirror(TreeNode *pRoot) {
        if (pRoot == NULL) {
            return ;
        }
        TreeNode* pTmp = pRoot->left;
        pRoot->left = pRoot->right;
        pRoot->right = pTmp;
        
        if (pRoot->left != NULL) {
            Mirror(pRoot->left);
        }
        if (pRoot->right != NULL) {
            Mirror(pRoot->right);
        }
    }
};

19. 顺时针打印矩阵

• 输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字，例如，如果输入如下矩阵： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 则依次打印出数字1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10.

class Solution {
public:
    vector<int> printMatrix(vector<vector<int> > matrix) {
        vector<int> res;
        int rows = matrix.size();
        int cols = matrix[0].size();
        if (rows <=0 || cols <= 0) {
            return res;
        }
        
        int start = 0;
        while (cols > start*2 && rows > start*2) {
            res = circleMatrix(matrix, cols, rows, start, res);
            start ++;
        }
        return res;
    }
    
    vector<int> circleMatrix(vector<vector<int> > matrix, int cols, int rows, 
                            int start, vector<int> res) {
        int endX = cols-1-start;
        int endY = rows-1-start;
        
        // 从左到右打印一行
        for (int i = start; i <= endX; i ++) {
            res.push_back(matrix[start][i]);
        }
        
        // 从上倒下打印一列，先判断是否需要打印这一列
        if (start < endY) {
            for (int i = start+1; i <= endY; i ++) {
                res.push_back(matrix[i][endX]);
            }
        }
        
        // 从右到左打印一行，先判断是否有这一行
        if (start < endY && start < endX) {
            for (int i = endX-1; i >= start; i --) {
                res.push_back(matrix[endY][i]);
            }
        }
        
        // 从下到上打印一行，先判断是否需要打印
        if (start < endX && start < endY-1) {
            for (int i = endY-1; i > start; i --) {
                res.push_back(matrix[i][start]);
            }
        }
        return res;
    }
};

20. 包含min函数的栈

• 定义栈的数据结构，请在该类型中实现一个能够得到栈最小元素的min函数。

// Solution:使用辅助栈同步保存当前最小值记录
class Solution {
private:
    stack<int> data;
    stack<int> data_min;
public:
    void push(int value) {
        data.push(value);
        if (data_min.size() == 0 || data_min.top() > value) {
            data_min.push(value);
        } else {
            data_min.push(data_min.top());
        }
    }
    void pop() {
        data.pop();
        data_min.pop();
    }
    int top() {
        return data.top();
    }
    int min() {
       return data_min.top();
    }
};