CCI_chapter 4 trees and Grapths

时间:2022-05-06 09:24:43

4.1Implement a function to check if a tree is balanced For the purposes of this question,a balanced tree is defned to be a tree such that no two leaf nodes difer in distance from the root by more than one

http://www.cnblogs.com/graph/archive/2013/04/12/3016433.html

4.2DFS

4.3Given a sorted (increasing order) array, write an algorithm to create a binary tree with  minimal height

http://www.cnblogs.com/graph/p/3184984.html

4.4 Given a binary search tree, design an algorithm which creates a linked list of all the nodes at each depth (eg, if you have a tree with depth D, you’ll have D linked lists)

http://www.cnblogs.com/graph/p/3251831.html

题目类似,就不多做了

4.5Write an algorithm to fnd the ‘next’ node (e g , in-order successor) of a given node in a binary search tree where each node has a link to its parent

struct Node
{
int data;
struct Node* left;
struct Node* right;
struct Node* parent;
};
Node * minNode(Node * cur){ while(NULL != cur->left){
cur = cur->left;
}
return cur; }
Node * inOrderSucc(Node *cur){
if(cur == NULL) return NULL;
if(NULL != cur->right)
return minNode(cur->right); Node * p = cur->parent;
while(NULL != p && p->right == cur){
cur = p;
p = p->parent;
} return p; }

reference : http://www.geeksforgeeks.org/inorder-successor-in-binary-search-tree/(不喜欢CCI上的渣渣答案)

4.6Design an algorithm and write code to fnd the frst common ancestor of two nodes in a binary tree Avoid storing additional nodes in a data structure NOTE: This is not 

necessarily a binary search tree

http://www.cnblogs.com/graph/p/3271292.html

4.7 You have two very large binary trees: T1, with millions of nodes, and T2, with hundreds of nodes Create an algorithm to decide if T2 is a subtree of T1

无聊的一道题,解法完全没有体现出来大数据

/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
bool isMatch(TreeNode * T1, TreeNode &T2);
bool isSubtree(TreeNode *T1, TreeNode *T2){ if(T2 == NULL) return true;
if(NULL == T1) return false;
if(T1->val == T2->val && ismatch(T1, T2)){
return true;
}
return isSubtree(T1->left , T2) || isSubtree(T1->right, T2) ; }
bool isMatch(TreeNode * T1, TreeNode &T2){
if(T1 == NULL && T2 == NULL) return true;
if(T1 == NULL || T2 == NULL) return false; if(T1->val != T2->val) return false; return isMatch(T1->left , T2->right) && isMatch(T1->right, T2->right); }

4.8 You are given a binary tree in which each node contains a value Design an algorithm  to print all paths which sum up to that value Note that it can be any path in the tree

- it does not have to start at the root

CCI 给的答案实在不爽,明明就是一个后续遍历的应用。非要搞的莫名其妙的。

声明: 以下代码只是写出了我的思路,没有经过测试

struct Node{
int val;
Node * left;
Node * right;
Node(int value):val(value), left(NULL),right(NULL){}
};
void print(stack<int> s){
while(!s.empty()){
cout<<s.top() <<" ";
s.pop();
}
cout<<endl;
}
void findSum(Node *root,int sum, vector<stack<int>> &path, vector<stack <int>> &path_sum ){ if(root == NULL) return ;
if(root->left == NULL && root->right == NULL){
stack<int> p,s;
p.push(root->val);
s.push(root->val);
path.push_back(p);
path_sum.push_back(s);
return;
} vector<stack<int>> pathLeft, pathRight , sumLeft, sumRight;
if(root->left != NULL)
findSum(root->left, sum, pathLeft,sumLeft);
if(root->right != NULL)
findSum(root->right, sum, pathRight, sumRight); int cur = root->val;
for(int i = ; i < pathLeft.size(); i++)
{
pathLeft[i].push(cur);
int top = sumLeft[i].top() + cur;
sumLeft[i].push(top);
if(top == sum)
print(pathLeft[i]); path.push_back(pathLeft[i]);
path_sum.push_back(sumLeft[i]);
} for(int i = ; i< pathRight.size(); i++)
{
pathRight[i].push_back(cur);
int top = sumRight[i].top() + cur;
sumRight[i].push(top);
if(top == sum)
print(pathRight[i]); path.push_back(pathRight[i]);
path_sum.push_back(sumRight[i]);
}
}