Binary Tree
二叉树相关问题常常能用recursion解决，而且往往非常简单。要非常熟练。对应的iteration方法也要掌握。
Anytime when you found that doing top down approach uses a lot of repeated calculation, bottom up approach usually is able to be more efficient.
top-down，bottom-up， divide-conquer 常用思路
http://www.cnblogs.com/AnnieKim/archive/2013/06/15/morristraversal.html
1. Preorder traversal
1. Recersion
void preorderHelper(TreeNode *root, vector<TreeNode*> &nodelist) {
if(root == NULL) return;
nodelist.push_back(root);
preorder(root->left, nodelist);
preorder(root->right, nodelist);
}
1.2 Iteration
将根结点入栈； 每次从栈顶弹出一个结点，访问该结点； 把当前结点的右孩子入栈； 把当前结点的左孩子入栈。
void preorder(TreeNode *root, vector<TreeNode*> &nodelist) {
if(root == NULL) return;
stack<TreeNode*> mystk;
mystk.push(root);
while(!mystk.empty()) {
TreeNode *cur = mystk.top();
mystk.pop();
nodelist.push_back(cur);
if(cur->right) {
mystk.push(cur->right);
}
if(cur->left) {
mystk.push(cur->left);
}
}
}
1.3 Morris Traversal
步骤：
如果当前节点的左孩子为空，则输出当前节点并将其右孩子作为当前节点。
如果当前节点的左孩子不为空，在当前节点的左子树中找到当前节点在中序遍历下的前驱节点。
a) 如果前驱节点的右孩子为空，将它的右孩子设置为当前节点。输出当前节点（在这里输出，这是与中序遍历唯一一点不同）。当前节点更新为当前节点的左孩子。
b) 如果前驱节点的右孩子为当前节点，将它的右孩子重新设为空。当前节点更新为当前节点的右孩子。
重复以上1、2直到当前节点为空。
void preorder(TreeNode *root, vector<TreeNode*> &nodelist) {
if(root == NULL) return;
TreeNode *cur = root;
TreeNode *prev = nullptr;
while(cur) {
if(cur->left == nullptr) {//step 1
nodelist.push_back(cur);//output
cur = cur->right;
} else {//step 2
prev = cur->left;
while(prev->right != nullptr && prev->right != cur) {
prev = prev->right;//find previous in in-order tranvesal
}
if(prev->right == nullptr) {//step 2.1
nodelist.push_back(cur);//ouput
prev->right = cur;
cur = cur->left;
} else {//prev->right == cur step 2.2
cur = cur->right;
prev->right = nullptr;
}
}
}
}
2. Inorder Traversal
2.1 Recrusion
void inorderTraversalHelper(TreeNode *root, vector<int> &nodelist) {
if(root == NULL) return;
inorderTraversalHelper(root->left, nodelist);
nodelist.push_back(root->val);
inorderTraversalHelper(root->right, nodelist);
}
2.2 Itereation
- 初始化一个二叉树结点pNode指向根结点；
- 若pNode非空，那么就把pNode入栈，并把pNode变为其左孩子；（直到最左边的结点）
- 若pNode为空，弹出栈顶的结点，并访问该结点，将pNode指向其右孩子（访问最左边的结点，并遍历其右子树）
- 重复2和3直到pNode和stack都为空
vector<int> inorderTraversal(TreeNode *root) { // write your code here vector<int> result; TreeNode *cur = root; stack<TreeNode*> mystk; while(cur != NULL || !mystk.empty()) { if(cur != NULL) { mystk.push(cur); cur = cur->left; } else { cur = mystk.top(); mystk.pop(); result.push_back(cur->val); cur = cur->right; } } return result; }
2.3 Morris Traversal
如果当前节点的左孩子为空，则输出当前节点并将其右孩子作为当前节点。
如果当前节点的左孩子不为空，在当前节点的左子树中找到当前节点在中序遍历下的前驱节点。
a) 如果前驱节点的右孩子为空，将它的右孩子设置为当前节点。当前节点更新为当前节点的左孩子。跟前序不同，此时不输出。
b) 如果前驱节点的右孩子为当前节点，将它的右孩子重新设为空（恢复树的形状）。输出当前节点。当前节点更新为当前节点的右孩子。
重复以上1、2直到当前节点为空。
vector<int> inorderTraversal(TreeNode *root) {
// write your code here
vector<int> result;
TreeNode *cur = root;
TreeNode *prev = nullptr;
while(cur) {
if(cur->left == nullptr) {
result.push_back(cur->val);
cur = cur->right;
} else {
prev = cur->left;
while(prev->right != nullptr && prev->right != cur) {
prev = prev->right;
}
if(prev->right == nullptr) {
prev->right = cur;
cur = cur->left;
} else {
result.push_back(cur->val);
prev->right = nullptr;
cur = cur->right;
}
}
}
return result;
}
3. Postorder Traversal
3.1 Recursion
void postorder(TreeNode *root, vector<int> &result) {
if(root == NULL)
return;
postorder(root->left, result);
postorder(root->right, result);
result.push_back(root->val);
}
3.2 Iteration
class Solution {
/**
* @param root: The root of binary tree.
* @return: Postorder in vector which contains node values.
*/
public:
vector<int> postorderTraversal(TreeNode *root) {
// write your code here
stack<TreeNode*> mystk;
vector<int> result;
if(root == NULL)
return result;
mystk.push(root);
TreeNode*cur, *pre;
cur = root;
pre = root;
while (!mystk.empty()) {
cur = mystk.top();
if((cur->left == NULL && cur->right == NULL) || cur->right==pre
|| cur->left==pre) {
mystk.pop();
result.push_back(cur->val);
pre = cur;
} else {
if(cur->right)
mystk.push(cur->right);
if(cur->left)
mystk.push(cur->left);
}
}
}
};
3.3 Morrise traversal O(1) space
当前节点设置为临时节点dump。令其左孩子是root
如果当前节点的左孩子为空，则将其右孩子作为当前节点。
如果当前节点的左孩子不为空，在当前节点的左子树中找到当前节点在中序遍历下的前驱节点。
a) 如果前驱节点的右孩子为空，将它的右孩子设置为当前节点。当前节点更新为当前节点的左孩子。
b) 如果前驱节点的右孩子为当前节点，将它的右孩子重新设为空。倒序输出从当前节点的左孩子到该前驱节点这条路径上的所有节点。当前节点更新为当前节点的右孩子。
重复以上1、2直到当前节点为空。
class Solution {
/**
* @param root: The root of binary tree.
* @return: Postorder in vector which contains node values.
*/
public:
vector<int> postorderTraversal(TreeNode *root) {
// write your code here
vector<int> res;
TreeNode dummy(INT_MIN);
dummy.left = root;
TreeNode *curr = &dummy;
while (curr) {
if (!curr->left) {
curr = curr->right;
} else {
TreeNode *node = curr->left;
while (node->right && node->right != curr) {
node = node->right;
}
if (!node->right) {
node->right = curr;
curr = curr->left;
} else {
vector<int> v = trace_back(curr->left, node);
res.insert(res.end(), v.begin(), v.end());
node->right = nullptr;
curr = curr->right;
}
}
}
return res;
}
vector<int> trace_back(TreeNode *frm, TreeNode *to) {
vector<int> res;
TreeNode *curr = frm;
while (curr != to) {
res.emplace_back(curr->val);
curr = curr->right;
}
res.emplace_back(to->val);
reverse(res.begin(), res.end());
return res;
}
};
Follow UP. 上面trace_back函数返回一个vector，然后reverse it， insert at the end of result. vector的构建、revers、insert都要耗费时间，把from到to的nodes看成一个list，那就是链表反转问题了，反转以后直接emplace到result尾部，省去了专门的反转和insert，节省copy and move的时间。
void OutputFromTo(TreeNode *from, TreeNode *to, vector<int> &nodes) {
TreeNode *cur = from;
TreeNode dummy(INT_MIN);
dummy.right = cur;
TreeNode *prev = &dummy;
while(cur != to) {//reverse the node list "from =----- to"
TreeNode *tmp = cur->right;
cur->right = prev;
prev = cur;
cur = tmp;
}
cur->right = prev;
while(cur != &dummy) {//output
nodes.push_back(cur->val);
cur = cur->right;
}
}