程序员面试经典chapter4 Trees and Graphs

第一题 二叉树平衡检查

题目描述： 检查二叉树是否平衡，对于任意一个节点来说两个子树的高度差小于1
题目给出的函数为

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

遍历方式应该用后序(post-order)先左边再右边最后到根，所以当判断根节点是否平衡的时候就判断下一个depth节点是否平衡，以此类推。用递归的的方式来判断平衡，不要多次计算子节点，子树的高度。主要函数以递归的形式求深一层的节点平衡，一个utility函数用来返回求得的当前节点的深度，所以最后通过代码为：

/*
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;
    }
};

第二题 有向路径检查

题目描述：检查一个有向图中两个节点之间是否有 有向路径
题目给出的结构体为：

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

单纯的想象，肯定还是遍历了，至于说是深度优先还是广度优先，我一开始也不知道，凭直觉来做，很简单。

从节点a指向节点b(a->b)，建立一个循环知会每一个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，你猜怎样，那就是有向咯，那如果不是，就要从隔壁邻居的隔壁邻居开始找，所以我需要一个可以先进先出的结构，队列。
也就是说在循环a的隔壁邻居之后(a->neighbour)，再从刚才的第一个隔壁邻居开始继续寻找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();
        }

回到最开始的问题，这就应该是广度优先遍历了图，因为并没有从单个的neighbour开始立即寻找该neighbour的下一个节点，而是在建立的循环中每次首先遍历周围所有的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;
    }
};

第三题 实现一个最小BST

题目描述：给定一个array，其中元素按照大小排列，创建一个高度最小的二叉查找树。
首先回顾一下什么是BST好了：

• 非子叶节点都只有两个子节点，分别是左儿子和右儿子
• 而每个非子叶节点的左儿子小于该非子叶节点，该非子叶节点又比右儿子小

因为已经既定了一个从小到大排列的数组，那就从中间开始作为该二叉树的根节点，每次insert左儿子(←)和右儿子(→)的时候就正好将前半段与后半段相应的继续递归添加。
其实...好像并没有最小这一说，总之通过代码很简单，在这里：

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]);//根节点
        int left, right;//左右子树
        midroot->left = addToTree(vals, start, mid - 1, left);//左子树
        midroot->right = addToTree(vals, mid + 1, end, right);//右子树
        n = (left >= right ? left : right) + 1;//计算当前高度
        return midroot;
    }
};

第四题 检查是否为BST

题目描述：实现一个函数检查一个给定二叉树是否为查找二叉树
题目给定结构体：

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

好吧，重复了刚才回顾的BST的定义，就一个非子叶节点来说满足两条：1. 左儿子和右儿子；2.左儿子比该节点小，右儿子比该节点大

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

所以最终通过代码为：

/*
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);
    }
};