第一题 二叉树平衡检查
题目描述： 检查二叉树是否平衡，对于任意一个节点来说两个子树的高度差小于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);
}
};
