剑桥offer（51~60）

51.题目描述

给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。

/*

struct TreeLinkNode {

    int val;

    struct TreeLinkNode *left;

    struct TreeLinkNode *right;

    struct TreeLinkNode *next;

    TreeLinkNode(int x) :val(x), left(NULL), right(NULL), next(NULL) {

    }

};

*/

class Solution {

    TreeLinkNode* getNode(TreeLinkNode* pNode){

        TreeLinkNode*pre = NULL;

        while (pNode){

            pre = pNode;

            pNode = pNode->left;

        }

        return pre;

    }

public:

    TreeLinkNode* GetNext(TreeLinkNode* pNode)

    {

        TreeLinkNode*tmp = pNode->next;

        if (tmp){//如果有父节点

            if (tmp->left == pNode&&pNode->right == NULL){//如果是左节点，就返回他的爸爸

                return tmp;

            }

            else if (tmp->left == pNode&&pNode->right != NULL){

                return getNode(pNode->right);

            }

            if (tmp->right == pNode){//如果是右节点，就返回他的右儿子

                if (pNode->right){

                    return getNode(pNode->right);

                }

                else if (tmp->next->left == tmp){

                    return tmp->next;

                }

                else if (tmp->next->right == tmp){

                    return NULL;

                }

            }

        }

        else{//根节点

            return getNode(pNode->right);

        }

        return NULL;

    }

};

52.题目描述

请实现一个函数，用来判断一颗二叉树是不是对称的。注意，如果一个二叉树同此二叉树的镜像是同样的，定义其为对称的。

/*

struct TreeNode {

    int val;

    struct TreeNode *left;

    struct TreeNode *right;

    TreeNode(int x) :

            val(x), left(NULL), right(NULL) {

    }

};

*/

class Solution {

public:

    bool isSymmetrical(TreeNode* pRoot)

    {

        return isSymmetrical(pRoot,pRoot);

    }

    bool isSymmetrical(TreeNode* pRoot1,TreeNode* pRoot2)

    {

        if(pRoot1==NULL&&pRoot2==NULL)

            return true;

        if(pRoot1==NULL || pRoot2==NULL)

            return false;

        if(pRoot1->val!=pRoot2->val)

            return false;

        return isSymmetrical(pRoot1->left,pRoot2->right) && isSymmetrical(pRoot1->right,pRoot2->left);

    }

};

53.题目描述

请实现一个函数按照之字形打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，其他行以此类推。

不使用reverse!!! 借助两个stack，分别为s1和s2。

1. 首先将根节点压入栈s1。

2. 将s1依次出栈，保存每个节点值，并依次将每个节点的左右节点压入栈s2

3. 将s2依次出栈，保存每个节点值，并依次将每个节点的右左节点压入本s1<注：这里是先压右子

节点再压左子节点>

/*

struct TreeNode {

    int val;

    struct TreeNode *left;

    struct TreeNode *right;

    TreeNode(int x) :

            val(x), left(NULL), right(NULL) {

    }

};

*/

class Solution {

public:

    vector<vector<int> > Print(TreeNode* pRoot) {

         vector<vector<int> > result;

        if (!pRoot) { return result; }

        stack<TreeNode*> s1;

        stack<TreeNode*> s2;

        vector<int> temp;

        s1.push(pRoot);

        while (true) {

            while (!s1.empty()) {

                TreeNode* ptr = s1.top();

                s1.pop();

                if (!ptr) { continue; }

                s2.push(ptr->left);

                s2.push(ptr->right);

                temp.push_back(ptr->val);

            }

            if (temp.empty()) { break; }

            result.push_back(temp);

            temp.clear();

            while (!s2.empty()) {

                TreeNode* ptr = s2.top();

                s2.pop();

                if (!ptr) { continue; }

                s1.push(ptr->right);

                s1.push(ptr->left);

                temp.push_back(ptr->val);

            }

            if (temp.empty()) { break; }

            result.push_back(temp);

            temp.clear();

        }

        return result;

    }

};

54.题目描述

从上到下按层打印二叉树，同一层结点从左至右输出。每一层输出一行。

/*

struct TreeNode {

    int val;

    struct TreeNode *left;

    struct TreeNode *right;

    TreeNode(int x) :

            val(x), left(NULL), right(NULL) {

    }

};

*/

class Solution {

public:

        vector<vector<int> > Print(TreeNode* pRoot) {

            queue<TreeNode*>qu1;

            queue<TreeNode*>qu2;

            vector<int> a;

            vector<vector<int> >as;

            if(!pRoot)

                return as;

            qu1.push(pRoot);

            while(){

                while(!qu1.empty()){

                   TreeNode*  tmp=qu1.front();

                    qu1.pop();

                    if(!tmp)continue;

                    a.push_back(tmp->val);

                    qu2.push(tmp->left);

                    qu2.push(tmp->right);

                }

                if(a.empty()){break;}

                as.push_back(a);

                a.clear();

                while(!qu2.empty()){

                   TreeNode*  tmp=qu2.front();

                    qu2.pop();

                    if(!tmp)continue;

                    a.push_back(tmp->val);

                    qu1.push(tmp->left);

                    qu1.push(tmp->right);

                }

                if(a.empty()){break;}

                as.push_back(a);

                a.clear();

            }

            return as;

        }

};

55.题目描述

请实现两个函数，分别用来序列化和反序列化二叉树

/*

struct TreeNode {

    int val;

    struct TreeNode *left;

    struct TreeNode *right;

    TreeNode(int x) :

            val(x), left(NULL), right(NULL) {

    }

};

*/

class Solution {

private:

    TreeNode* decode(char *&str) {

        if(*str=='#'){

            str++;

            return NULL;

        }

        int num = ;

        while(*str != ',')

            num = num* + (*(str++)-'');

        str++;

        TreeNode *root = new TreeNode(num);

        root->left = decode(str);

        root->right = decode(str);

        return root;

    }

public:

    char* Serialize(TreeNode *root) {

        if(!root) return "#";

        string r = to_string(root->val);

        r.push_back(',');

        char *left = Serialize(root->left);

        char *right = Serialize(root->right);

        char *ret = new char[strlen(left) + strlen(right) + r.size()];

        strcpy(ret, r.c_str());

        strcat(ret, left);

        strcat(ret, right);

        return ret;

    }

    TreeNode* Deserialize(char *str) {

        return decode(str);

    }

};

56.题目描述

给定一颗二叉搜索树，请找出其中的第k大的结点。例如， 5 / \ 3 7 /\ /\ 2 4 6 8 中，按结点数值大小顺序第三个结点的值为4。

思路：中序遍历。

/*

struct TreeNode {

    int val;

    struct TreeNode *left;

    struct TreeNode *right;

    TreeNode(int x) :

            val(x), left(NULL), right(NULL) {

    }

};

*/

class Solution {

public:

    TreeNode* KthNode(TreeNode* pRoot, int k)

    {

        vector<TreeNode*>a;

        stack<TreeNode*>stack;

        TreeNode* p = pRoot;

        while(p || !stack.empty()){

            if(p!=NULL){

                stack.push(p);

                p = p->left;

            }else{

                p = stack.top();

                a.push_back(p);

                stack.pop();

                p = p ->right;

            }

        }

        if(k > a.size()){

            return NULL;

        }else if(k == ){

            return NULL;

        }else{

            return a[k-];

        }

    }

};

57.题目描述

如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。

class Solution {

    vector<int>a;

public:

    void Insert(int num)

    {

        a.push_back(num);

    }

    double GetMedian()

    {

        vector<int>b=a;

        sort(b.begin(), b.end());

        if(b.size()% == ){

            return b[b.size()/];

        }else{

            return (b[b.size()/]+b[b.size()/-])/2.0;

        }

    }

};

58.题目描述

给定一个数组和滑动窗口的大小，找出所有滑动窗口里数值的最大值。例如，如果输入数组{2,3,4,2,6,2,5,1}及滑动窗口的大小3，那么一共存在6个滑动窗口，他们的最大值分别为{4,4,6,6,6,5}；针对数组{2,3,4,2,6,2,5,1}的滑动窗口有以下6个： {[2,3,4],2,6,2,5,1}， {2,[3,4,2],6,2,5,1}， {2,3,[4,2,6],2,5,1}， {2,3,4,[2,6,2],5,1}， {2,3,4,2,[6,2,5],1}， {2,3,4,2,6,[2,5,1]}。

class Solution {

    int getVal(vector<int>v){

        int max = v[];

        for (int i = ; i<v.size(); i++){

            if (max < v[i]){

                max = v[i];

            }

        }

        return max;

    }

public:

    vector<int> maxInWindows(const vector<int>& num, unsigned int size)

    {

        vector<int>a;

        vector<int>tmp;

        if (num.size()<size||size == )

            return a;

        for (int i = ; i<num.size() - size+; i++){

            for (int j = ; j<size; j++){

                tmp.push_back(num[j + i]);

            }

            a.push_back(getVal(tmp));

            tmp.clear();

        }

        return a;

    }

};

59.题目描述

请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。如果一条路径经过了矩阵中的某一个格子，则该路径不能再进入该格子。例如 a b c e s f c s a d e e 矩阵中包含一条字符串"bccced"的路径，但是矩阵中不包含"abcb"路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入该格子。

60.题目描述

地上有一个m行和n列的方格。一个机器人从坐标0,0的格子开始移动，每一次只能向左，右，上，下四个方向移动一格，但是不能进入行坐标和列坐标的数位之和大于k的格子。例如，当k为18时，机器人能够进入方格（35,37），因为3+5+3+7 = 18。但是，它不能进入方格（35,38），因为3+5+3+8 = 19。请问该机器人能够达到多少个格子？

巴特西