一、
class Solution {
public:
TreeNode *lowestCommonAncestor(TreeNode *root, TreeNode *A, TreeNode *B) {
if (root == NULL || root == A || root == B) {
return root;
}
TreeNode* left = lowestCommonAncestor(root->left, A, B);
TreeNode* right = lowestCommonAncestor(root->right, A, B);
if (left != NULL && right != NULL) {
return root;
}
if (left != NULL) {
return left;
}
if (right != NULL) {
return right;
}
return NULL;
}
};
refer : July，剑指offer
2. Lowest Common Ancestor of a Binary Search Tree
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if (root == NULL || p == NULL || q == NULL) {
return NULL;
}
if (root->val > p->val && root->val > q->val) {
return lowestCommonAncestor(root->left, p, q);
}
if (root->val < p->val && root->val < q->val) {
return lowestCommonAncestor(root->right, p, q);
}
return root;
}
};
二. Level order [BFS]
1. Binary Tree Level Order Traversal
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>> result;
if (root == NULL) {
return result;
}
queue<TreeNode*> q;
q.push(root);
while(!q.empty()) {
int size = q.size();
vector<int> v;
for (int i = ; i < size; i++) {
TreeNode* tmp = q.front();
q.pop();
v.push_back(tmp->val);
if (tmp->left != NULL) {
q.push(tmp->left);
}
if (tmp->right != NULL) {
q.push(tmp->right);
}
}
result.push_back(v);
}
return result;
}
};
2. Binary Tree Level Order Traversal II
class Solution {
public:
vector<vector<int>> levelOrderBottom(TreeNode* root) {
vector<vector<int>> result;
if (root == NULL) {
return result;
}
queue<TreeNode*> q;
q.push(root);
while(!q.empty()) {
int size = q.size();
vector<int> v;
for (int i = ; i < size; i++) {
TreeNode* tmp = q.front();
q.pop();
v.push_back(tmp->val);
if (tmp->left != NULL) {
q.push(tmp->left);
}
if (tmp->right != NULL) {
q.push(tmp->right);
}
}
result.push_back(v);
}
reverse(result.begin(), result.end());
return result;
}
};
在1的基础上多加一句reverse即可。
3. Binary Tree Zigzag Level Order Traversal
class Solution {
public:
vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
vector<vector<int>> result;
if (root == NULL) {
return result;
}
queue<TreeNode*> q;
q.push(root);
int count = ;
while(!q.empty()) {
count++;
int size = q.size();
vector<int> v;
for (int i = ; i < size; i++) {
TreeNode* tmp = q.front();
q.pop();
v.push_back(tmp->val);
if (tmp->left != NULL) {
q.push(tmp->left);
}
if (tmp->right != NULL) {
q.push(tmp->right);
}
}
if (count % == ) {
reverse(v.begin(), v.end());
}
result.push_back(v);
}
return result;
}
};
在1的基础上多加个count变量，偶数行就reverse一下即可
三、
1. Insert Node in a Binary Search Tree
TreeNode* insertNode(TreeNode* root, TreeNode* node) {
if (root == NULL) {
return node;
}
if (node->val > root->val) {
root->right = insertNode(root->right, node);
} else {
root->left = insertNode(root->left, node);
}
return root;
}
2. Search Range in Binary Search Tree
code1:
class Solution {
public:
vector<int> searchRange(TreeNode* root, int k1, int k2) {
helper(root, k1, k2);
return result;
}
void helper(TreeNode* root, int k1, int k2) {
if (root == NULL) {
return;
}
if (k1 < root->val) {//说明左子树里有可能有
helper(root->left, k1, k2);
}
if (root->val >= k1 && root->val <= k2) {
result.push_back(root->val);
}
if (k2 > root->val) {
helper(root->right, k1, k2);
}
}
private:
vector<int> result;
};
code2: 自己实现的，太繁琐。
vector<int> searchRange(TreeNode* root, int k1, int k2) {
vector<int> result;
if (root == NULL) {
return result;
}
if (root->val < k1) {
return searchRange(root->right, k1, k2);
}
if (root->val > k2) {
return searchRange(root->left, k1, k2);
}
if (root->val >= k1 && root->val <= k2) {
vector<int> tmp1 = searchRange(root->left, k1, root->val - );
vector<int> tmp2 = searchRange(root->right, root->val + , k2);
result.insert(result.end(), tmp1.begin(), tmp1.end());
result.push_back(root->val);
result.insert(result.end(), tmp2.begin(), tmp2.end());
}
return result;
}
Binary Search Tree Iterator
class BSTIterator {
public:
BSTIterator(TreeNode* root) {
pushAll(root);
}
bool hasNext() {
return (!myStack.empty());
}
int next() {
TreeNode* tmp = myStack.top();
myStack.pop();
pushAll(tmp->right);
return tmp->val;
}
private:
stack<TreeNode*> myStack;
void pushAll(TreeNode* node);
};
void BSTIterator::pushAll(TreeNode* node) {
while (node != NULL) {
myStack.push(node);
node = node->left;
}
}
/**
* Your BSTIterator will be called like this:
* BSTIterator i = BSTIterator(root);
* while (i.hasNext()) cout << i.next();
*/
Remove Node in Binary Search Tree
参见 ref十五
===================================================
对于n个数的数组，一个数x如果从左往右数是第k个数，那么从右往左数的话是第(n - k + 1)个数。