程序员面试经典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);
    }
};
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。

推荐阅读更多精彩内容

  • 疯狂java笔记之树和二叉树
    树的概述 树是一种非常常用的数据结构，树与前面介绍的线性表，栈，队列等线性结构不同，树是一种非线性结构 1.树的定...
    Jack921阅读 4,515评论 1赞 31
  • 图解红黑树
    红黑树（英语：Red–black tree）是一种自平衡二叉查找树，是在计算机科学中用到的一种数据结构，典型的用途...
    卡巴拉的树阅读 15,301评论 11赞 113
  • 二叉树入门
    去年二叉树算法的事情闹的沸沸扬扬，起因是Homebrew 的作者 @Max Howell 在 twitter 上发...
    Masazumi柒阅读 1,636评论 0赞 8
  • OC二叉树相关操作
    二叉树-你必须要懂！（二叉树相关算法实现-iOS） http://www.cnblogs.com/manji/p/...
    汉秋阅读 1,895评论 0赞 16
  • 每日名言摘录第158期
    在这里，希望喜欢它的人一起每日感悟人生哲理，为你的生活多一点改变。 1、夜，有它特别的气息，寂静，有它自己的声音。...
    林窗鲸落阅读 306评论 0赞 0