Binary Tree BFS Traversal
二叉树层次遍历
//刚开始没看懂，自己画图细看几遍发生特别精妙，赞一个
//一定要记住队列是先进先出的
void levelTraversal(TreeNode *root)
{
queue<TreeNode *> nodeQueue;
TreeNode *currentNode;
if (!root) {
return;
}
//先塞入根节点
nodeQueue.push(root);
while (!nodeQueue.empty()) {
//当前节点值为queue中的第一个数据。
currentNode = nodeQueue.front();
//做进一步的处理，比如需要打印
processNode(currentNode);
if (currentNode->left) {
nodeQueue.push(currentNode->left);
}
if (currentNode->right) {
nodeQueue.push(currentNode->right);
}
//弹出当前的数据
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.
核心问题：如何判断这一层已经遍历完毕？
解题思路：利用优先队列
代码示例：
//为什么你老是喜欢把你定义的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()) {
//若首节点时dummyNode且level不为空，就将该level塞入我们的最终结果列表
//然后清空level。代表了一层遍历的结束，开始遍历二叉树的下一层
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
//利用两个变量来判断一层是否遍历完，标志位为nodesInCurrentLevel，
//当其为0时一层遍历结束，输入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
//使用队列来判断，当currentLevel时一层遍历结束
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)是二叉树的一种特例，对于二分查找树的任意节点，该节点储存的数值一定比左子树的所有节点的值大比右子树的所有节点的值小(该节点储存的数值一定比左子树的所有节点的值小比右子树的所有节点的值大)。基于这个特性，二分查找树通常被用于维护有序数据。二分查找树查找、删除、插入的效率都会高于一般的线性数据结构。
bst
平衡二叉树的概念。所谓平衡二叉树，是指一棵树的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。
有序数组变为二分查找树
代码示例：
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个英文字母)叉树，用于在一个集合中检索一个字符串，或者字符串前缀。字典树的每个节点有一个指针数组代表其所有子树，其本质上是一个hash table，因为子树所在的位置(index)本身，就代表了节点对应的字母。节点与每个兄弟具有相同的前缀，也被称为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
**********/
网友评论