第一題 二叉樹(shù)平衡檢查

題目描述： 檢查二叉樹(shù)是否平衡鸟废，對(duì)于任意一個(gè)節(jié)點(diǎn)來(lái)說(shuō)兩個(gè)子樹(shù)的高度差小于1
題目給出的函數(shù)為

class Balance {
public:
    bool isBalance(TreeNode* root) {
        // write code here
    }
};

遍歷方式應(yīng)該用后序(post-order)先左邊再右邊最后到根偶翅，所以當(dāng)判斷根節(jié)點(diǎn)是否平衡的時(shí)候就判斷下一個(gè)depth節(jié)點(diǎn)是否平衡，以此類推朱监。用遞歸的的方式來(lái)判斷平衡庵楷，不要多次計(jì)算子節(jié)點(diǎn)踪央，子樹(shù)的高度。主要函數(shù)以遞歸的形式求深一層的節(jié)點(diǎn)平衡渊额，一個(gè)utility函數(shù)用來(lái)返回求得的當(dāng)前節(jié)點(diǎn)的深度况木，所以最后通過(guò)代碼為：

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};*/

class Balance {
public:
    bool isBalance(TreeNode* root) {
        if(root == NULL)
            return true;
        // write code here
        if((depth(root->left)-depth(root->right)>1) || (depth(root->left)-depth(root->right)<-1))
           return false;
        else
            return isBalance(root->left)&&isBalance(root->right);
    }
     
    int depth(TreeNode* root){
        if(root == NULL)
            return 0;
        return depth(root->left)>depth(root->right)? depth(root->left)+1:depth(root->right)+1;
    }
};

第二題 有向路徑檢查

題目描述：檢查一個(gè)有向圖中兩個(gè)節(jié)點(diǎn)之間是否有 有向路徑
題目給出的結(jié)構(gòu)體為：

struct UndirectedGraphNode {
    int label;
    vector<struct UndirectedGraphNode *> neighbors;
    UndirectedGraphNode(int x) : label(x) {}
};

單純的想象垒拢，肯定還是遍歷了，至于說(shuō)是深度優(yōu)先還是廣度優(yōu)先火惊，我一開(kāi)始也不知道求类，憑直覺(jué)來(lái)做，很簡(jiǎn)單屹耐。

從節(jié)點(diǎn)a指向節(jié)點(diǎn)b(a->b)尸疆，建立一個(gè)循環(huán)知會(huì)每一個(gè)a的neighbour，首先判斷a的neighbour是否是b惶岭。

queue<UndirectedGraphNode*> que;
        map<UndirectedGraphNode*,bool> map1;
        //que.push(a);
        while(!que.empty()){
            //UndirectedGraphNode* ptr=que.front();
            map1[ptr]=true;
            for(int i=0;i<ptr->neighbors.size();i++)
            {
                if((ptr->neighbors)[i]==b){...}
            }

如果隔壁鄰居正好是b寿弱，你猜怎樣，那就是有向咯按灶，那如果不是症革，就要從隔壁鄰居的隔壁鄰居開(kāi)始找，所以我需要一個(gè)可以先進(jìn)先出的結(jié)構(gòu)鸯旁，隊(duì)列噪矛。
也就是說(shuō)在循環(huán)a的隔壁鄰居之后(a->neighbour)，再?gòu)膭偛诺牡谝粋€(gè)隔壁鄰居開(kāi)始繼續(xù)尋找a隔壁的隔壁的鄰居...以此類推铺罢。

while(!que.empty()){
           UndirectedGraphNode* ptr=que.front();
            map1[ptr]=true;
            for(int i=0;i<ptr->neighbors.size();i++)
            {
                if((ptr->neighbors)[i]==b)
                    return true;
                if(ptr->neighbors[i]&&map1[ptr->neighbors[i]]!=true)
                    que.push((ptr->neighbors)[i]);
            }
            que.pop();
        }

回到最開(kāi)始的問(wèn)題艇挨，這就應(yīng)該是廣度優(yōu)先遍歷了圖，因?yàn)椴](méi)有從單個(gè)的neighbour開(kāi)始立即尋找該neighbour的下一個(gè)節(jié)點(diǎn)韭赘，而是在建立的循環(huán)中每次首先遍歷周圍所有的neighbour缩滨。
下面是完整代碼：

/*
struct UndirectedGraphNode {
    int label;
    vector<struct UndirectedGraphNode *> neighbors;
    UndirectedGraphNode(int x) : label(x) {}
};*/

class Path {
public:
    bool checkPath(UndirectedGraphNode* a, UndirectedGraphNode* b) {
        // write code here
        return check(a,b)||check(b,a);
    }
    bool check(UndirectedGraphNode* a, UndirectedGraphNode* b){
        if(a==NULL||b==NULL)
            return false;
        if(a==b)
            return true;
        queue<UndirectedGraphNode*> que;
        map<UndirectedGraphNode*,bool> map1;
        que.push(a);
        while(!que.empty()){
           UndirectedGraphNode* ptr=que.front();
            map1[ptr]=true;
            for(int i=0;i<ptr->neighbors.size();i++)
            {
                if((ptr->neighbors)[i]==b)
                    return true;
                if(ptr->neighbors[i]&&map1[ptr->neighbors[i]]!=true)
                    que.push((ptr->neighbors)[i]);
            }
            que.pop();
        }
        return false;
    }
};

第三題 實(shí)現(xiàn)一個(gè)最小BST

題目描述：給定一個(gè)array，其中元素按照大小排列辞居，創(chuàng)建一個(gè)高度最小的二叉查找樹(shù)楷怒。
首先回顧一下什么是BST好了：

• 非子葉節(jié)點(diǎn)都只有兩個(gè)子節(jié)點(diǎn)蛋勺，分別是左兒子和右兒子
• 而每個(gè)非子葉節(jié)點(diǎn)的左兒子小于該非子葉節(jié)點(diǎn)瓦灶，該非子葉節(jié)點(diǎn)又比右兒子小

因?yàn)橐呀?jīng)既定了一個(gè)從小到大排列的數(shù)組，那就從中間開(kāi)始作為該二叉樹(shù)的根節(jié)點(diǎn)抱完，每次insert左兒子(←)和右兒子(→)的時(shí)候就正好將前半段與后半段相應(yīng)的繼續(xù)遞歸添加贼陶。
其實(shí)...好像并沒(méi)有最小這一說(shuō)，總之通過(guò)代碼很簡(jiǎn)單巧娱，在這里：

class MinimalBST {
public:
    int buildMinimalBST(vector<int> vals) {
        // write code here
        int height=0;
        addToTree(vals, 0, vals.size() - 1, height);
        return height;
    }
    TreeNode *addToTree(vector<int> vals,int start,int end,int& n){
        if(end<start){
            n=0;
            return NULL;
        }
        int mid = start + (end - start) / 2;
        TreeNode *midroot = new TreeNode(vals[mid]);//根節(jié)點(diǎn)
        int left, right;//左右子樹(shù)
        midroot->left = addToTree(vals, start, mid - 1, left);//左子樹(shù)
        midroot->right = addToTree(vals, mid + 1, end, right);//右子樹(shù)
        n = (left >= right ? left : right) + 1;//計(jì)算當(dāng)前高度
        return midroot;
    }
};

第四題 檢查是否為BST

題目描述：實(shí)現(xiàn)一個(gè)函數(shù)檢查一個(gè)給定二叉樹(shù)是否為查找二叉樹(shù)
題目給定結(jié)構(gòu)體：

struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};

好吧碉怔，重復(fù)了剛才回顧的BST的定義，就一個(gè)非子葉節(jié)點(diǎn)來(lái)說(shuō)滿足兩條：1. 左兒子和右兒子禁添；2.左兒子比該節(jié)點(diǎn)小撮胧，右兒子比該節(jié)點(diǎn)大

root->left->val < root->val
root->right->val > root->val

所以最終通過(guò)代碼為：

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};*/

class Checker {
public:
    bool checkBST(TreeNode* root) {
        // write code here
        if(root==NULL)
            return true;
         
        if(root->left!=NULL){
            if(root->left->val>root->val)
                return false;
            if(root->left->right!=NULL&&root->left->right->val>root->val)
                return false;
        }
         
        if(root->right!=NULL&&root->right->val<root->val)
            return false;
             
        return checkBST(root->left) && checkBST(root->right);
    }
};