Binary Tree BFS Traversal
二叉樹層次遍歷
//剛開始沒看懂衣屏，自己畫圖細看幾遍發(fā)生特別精妙，贊一個
//一定要記住隊列是先進先出的
void levelTraversal(TreeNode *root)
{
queue<TreeNode *> nodeQueue;
TreeNode *currentNode;
if (!root) {
return;
}
//先塞入根節(jié)點
nodeQueue.push(root);
while (!nodeQueue.empty()) {
//當(dāng)前節(jié)點值為queue中的第一個數(shù)據(jù)恬口。
currentNode = nodeQueue.front();
//做進一步的處理者春，比如需要打印
processNode(currentNode);
if (currentNode->left) {
nodeQueue.push(currentNode->left);
}
if (currentNode->right) {
nodeQueue.push(currentNode->right);
}
//彈出當(dāng)前的數(shù)據(jù)
nodeQueue.pop();
}
}
Binary Tree to Linked Lists
Covert a binary tree to linked lists. Each linked list is correspondent to all the nodes at the same level.
核心問題：如何判斷這一層已經(jīng)遍歷完畢？
解題思路：利用優(yōu)先隊列
代碼示例：
//為什么你老是喜歡把你定義的result寫成answer，我真的要報警了
ool isDummyNode(TreeNode *node) {
return (node->left == node);
}
vector<list<TreeNode *>> linkedListsFromTree(TreeNode *root) {
vector<list<TreeNode *>> result;
list<TreeNode *> levelList;
queue<TreeNode *> nodeQueue;
TreeNode *currentNode;
TreeNode dummyNode;
dummyNode.left = &dummyNode;
if (!root) {
return result;
}
nodeQueue.push(&dummyNode);//dummyNode用于分割層
nodeQueue.push(root);
while (!nodeQueue.empty()) {
currentNode = nodeQueue.front();
if (isDummyNode(currentNode)) {
if (!levelList.empty()) {
//若首節(jié)點時dummyNode且level不為空拍顷，就將該level塞入我們的最終結(jié)果列表
//然后清空level正蛙。代表了一層遍歷的結(jié)束督弓，開始遍歷二叉樹的下一層
result.push_back(levelList);
levelList.clear();
}
nodeQueue.pop();
if (nodeQueue.empty()) {
break;
} else {
//每次遍歷完一層，nodeQueue都會被塞入一個dummyNode
nodeQueue.push(&dummyNode);
}
} else {
levelList.push_back(currentNode);
if (currentNode->left) {
nodeQueue.push(currentNode->left);
}
if (currentNode->right) {
nodeQueue.push(currentNode->right);
}
nodeQueue.pop();
}
}
return result;
}
Binary Tree Level Order Traversal
- 2 Queues
- 1 Queue + Dummy Node
- 1 Queue (best)
示例代碼：
// use 2 variables
//利用兩個變量來判斷一層是否遍歷完乒验，標(biāo)志位為nodesInCurrentLevel愚隧，
//當(dāng)其為0時一層遍歷結(jié)束，輸入endl換行
void printLevelOrder(BinaryTree *root) {
if (!root) return;
queue<BinaryTree*> nodesQueue;
int nodesInCurrentLevel = 1;
int nodesInNextLevel = 0;
nodesQueue.push(root);
while (!nodesQueue.empty()) {
BinaryTree *currNode = nodesQueue.front();
nodesQueue.pop();
nodesInCurrentLevel--;
if (currNode) {
cout << currNode->data << " ";
nodesQueue.push(currNode->left);
nodesQueue.push(currNode->right);
nodesInNextLevel += 2;
}
if (nodesInCurrentLevel == 0) {
cout << endl;
nodesInCurrentLevel = nodesInNextLevel;
nodesInNextLevel = 0;
}
}
}
// use 2 queue
//使用隊列來判斷锻全，當(dāng)currentLevel時一層遍歷結(jié)束
void printLevelOrder(BinaryTree *root) {
if (!root) return;
queue<BinaryTree*> currentLevel, nextLevel;
currentLevel.push(root);
while (!currentLevel.empty()) {
BinaryTree *currNode = currentLevel.front();
currentLevel.pop();
if (currNode) {
cout << currNode->data << " ";
nextLevel.push(currNode->left);
nextLevel.push(currNode->right);
}
if (currentLevel.empty()) {
cout << endl;
swap(currentLevel, nextLevel);
}
}
}
Binary Tree Level Order Traversal II
Given a binary tree, return the bottom-up level order traversal of its nodes'values. (ie, from left to right, level by level from leaf to root).
For example: Given binary tree {3,9,20,#,#,15,7},
反式
return its bottom-up level order traversal as:
反式1
Binary Tree Zigzag Level Order Traversal
示例代碼：
void printLevelOrderZigZag(BinaryTree *root) {
stack<BinaryTree*> currentLevel, nextLevel;
bool leftToRight = true;
currentLevel.push(root);
while (!currentLevel.empty()) {
BinaryTree *currNode = currentLevel.top();
currentLevel.pop();
if (currNode) {
cout << currNode->data << " ";
if (leftToRight) {
nextLevel.push(currNode->left);
nextLevel.push(currNode->right);
} else {
nextLevel.push(currNode->right);
nextLevel.push(currNode->left);
}
}
if (currentLevel.empty()) {
cout << endl;
leftToRight = !leftToRight;
swap(currentLevel, nextLevel);
}
}
}
Binary Search Tree
二分查找樹(Binary Search Tree, BST)是二叉樹的一種特例奸攻，對于二分查找樹的任意節(jié)點蒜危，該節(jié)點儲存的數(shù)值一定比左子樹的所有節(jié)點的值大比右子樹的所有節(jié)點的值小(該節(jié)點儲存的數(shù)值一定比左子樹的所有節(jié)點的值小比右子樹的所有節(jié)點的值大)。基于這個特性匈辱，二分查找樹通常被用于維護有序數(shù)據(jù)扣汪。二分查找樹查找、刪除响委、插入的效率都會高于一般的線性數(shù)據(jù)結(jié)構(gòu)。
bst
平衡二叉樹的概念窖梁。所謂平衡二叉樹赘风，是指一棵樹的左右兩個子樹的高度差的絕對值不超過1，并且左右兩個子樹都是一棵平衡二叉樹纵刘。
有序數(shù)組變?yōu)槎植檎覙?/h3>
代碼示例：
TreeNode* helper(vector<int>num, int first, int last){
if(first > last){
return NULL;
}
if (first == last) {
TreeNode* parent = new TreeNode(num[first]);
return parent;
}
int mid = (first + last) / 2;
TreeNode *leftchild = helper(num, first, mid - 1);
TreeNode *rightchild = helper(num, mid + 1, last);
TreeNode *parent = new TreeNode(num[mid]);
parent->left = leftchild;
parent->right = rightchild;
return parent;
}
TreeNode *sortedArrayToBST(vector<int> &num) {
if(num.size() == 0)
return NULL;
if(num.size() == 1){
TreeNode* parent = new TreeNode(num[0]);
return parent;
}
int first = 0;
int last = (int)num.size() - 1;
return helper(num, first, last);
}
Is Binary Search Tree
錯誤例子：
/************
10
/ \
5 15
/ \
6 20
*************/
bool isValidBST(TreeNode* root) {
if(root==NULL)
return true;
else if(root->left&&!root->right)
return isValidBST(root->left)&&(root->val>root->left->val);
else if(!root->left&&root->right)
return isValidBST(root->right)&&(root->val<root->right->val);
else if(root->left&&root->right)
return isValidBST(root->left)&&isValidBST(root->right)&&(root->val>root->left->val)&&(root->val<root->right->val);
else
return true;
}
正確示例
bool helper(TreeNode *root, int min, int max){
if(!root) return true;
if((root->val < max || (root->val == INT_MAX && root->right == NULL)) &&
(root->val > min || (root->val == INT_MIN && root->left == NULL)) &&
helper(root->left, min, root->val) &&
helper(root->right, root->val, max))
return true;
return false;
}
bool isValidBST(TreeNode *root) {
return helper(root, INT_MIN, INT_MAX);
}
Trie
字典樹(trie or prefix tree)是一個26(26個英文字母)叉樹邀窃，用于在一個集合中檢索一個字符串，或者字符串前綴假哎。字典樹的每個節(jié)點有一個指針數(shù)組代表其所有子樹瞬捕，其本質(zhì)上是一個hash table，因為子樹所在的位置(index)本身舵抹，就代表了節(jié)點對應(yīng)的字母肪虎。節(jié)點與每個兄弟具有相同的前綴，也被稱為prefix tree惧蛹。
Trie Structure
class TrieNode{
private:
T mContent;
vector<TrieNode*> mChildren;
public:
Node();
~Node();
friend class Trie;
};
class Trie{
public:
Trie();
~Trie();
void addWord(string s);
bool searchWord(string s);
void deleteWord(string s);
private:
TrieNode* root;
};
Mock Interview
Lowest Common Ancestor(LCA)
最近的公共銜接點
Given a binary tree and two nodes. Find the lowest common ancestor of the two nodes in the tree.
For example, the LCA of D & E is B.
lca
示例代碼：
TreeNode *commonAncestor(TreeNode *root, TreeNode *p, TreeNode *q) {
if (covers(root->left, p) && covers(root->left, q)) {
return commonAncestor(root->left, q, p);
}
if (covers(root->right, p) && covers(root->right, q)) {
return commonAncestor(root->right, q, p);
}
return root;
}
bool covers(TreeNode *root, TreeNode *p) {
if (root == NULL) {
return false;
}
if (root == p) {
return true;
}
return covers(root->left, p) || covers(root->right, p);
}
// bottom to top
TreeNode *lowestCommonAncestor(TreeNode *root, TreeNode *A, TreeNode *B) {
// return either A or B or NULL
if (NULL == root || root == A || root == B) return root;
TreeNode *left = lowestCommonAncestor(root->left, A, B);
TreeNode *right = lowestCommonAncestor(root->right, A, B);
// A and B are on both sides
if ((NULL != left) && (NULL != right)) return root;
// either left or right or NULL
return (NULL != left) ? left : right;
}
Homework:
Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).
For example, this binary tree is symmetric:
/************
1
/ \
2 2
/ \ / \
3 4 4 3
************/
But the following is not:
/**********
1
/ \
2 2
\ \
3 3
**********/
