LeetCode有如下traversal的题目，这里只说普通遍历：
Binary Tree Inorder Traversal
Binary Tree Level Order Traversal
Binary Tree Zigzag Level Order Traversal
Binary Tree Level Order Traversal II
Binary Tree Preorder Traversal
Binary Tree Postorder Traversal
Construct Binary Tree from Preorder and Inorder Traversal
Construct Binary Tree from Inorder and Postorder Traversal
基本思路有三种，第一种是trivial的递归，第二种是用stack，第三种是Morris。
- 用stack的方法分两种，一种直观的dfs像(1)，一种用lastpop(2)或prev(3)记录上一个节点以判断遍历路径。
- 方法(1)的思路是顺着往left走直到遇见NULL，从stack弹出一个往right挪动，继续往left走。
- 方法(2)的思路是，每次循环分push left(left不为NULL并且从上往下遍历)，push right(right不为NULL并且right不是上次遍历的店并且从左边遍历过来或者左边为NULL)，pop(其他情况)三种情况。
- 方法(3)的思路是，每次循环分为from up(如果left不为NULL，push left否则right不为NULL，push right), from left(若right不为空push right),from right(其他情况)三种情况。
1.Discuss区的summary：
https://leetcode.com/discuss/71943/preorder-inorder-and-postorder-iteratively-summarization
-
preorder
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
Deque<TreeNode> stack = new ArrayDeque<>();
TreeNode p = root;
while(!stack.isEmpty() || p != null) {
if(p != null) {
stack.push(p);
result.add(p.val); // Add before going to children
p = p.left;
} else {
TreeNode node = stack.pop();
p = node.right;
}
}
return result;
} -
inorder
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
Deque<TreeNode> stack = new ArrayDeque<>();
TreeNode p = root;
while(!stack.isEmpty() || p != null) {
if(p != null) {
stack.push(p);
p = p.left;
} else {
TreeNode node = stack.pop();
result.add(node.val); // Add after all left children
p = node.right;
}
}
return result;
}
3） postorder
public List<Integer> postorderTraversal(TreeNode root) {
LinkedList<Integer> result = new LinkedList<>();
Deque<TreeNode> stack = new ArrayDeque<>();
TreeNode p = root;
while(!stack.isEmpty() || p != null) {
if(p != null) {
stack.push(p);
result.addFirst(p.val); // Reverse the process of preorder
p = p.right; // Reverse the process of preorder
} else {
TreeNode node = stack.pop();
p = node.left; // Reverse the process of preorder
}
}
return result;
}
这个postorder用了取巧的方法，不如下面这种后序遍历的实现，这个很舒服：
//后序遍历的非递归实现
void BT_PostOrderNoRec(pBintree root)
{
stack<pBintree> s;
pBintree pre = NULL;
pBintree top = NULL;
while((root != NULL) || (!s.empty()))
{
if(root != NULL)
{
s.push(root);
root = root->left;
}
else
{
top = s.top();
if(top->right != NULL && top->right != pre)
root = top->right;
else
{
visit(top);
pre = top;
s.pop();
}
}
}
}
2.lastpop方法
https://leetcode.com/discuss/9736/accepted-code-with-explaination-does-anyone-have-better-idea
-
preorder
void preorder_traversal_iteratively(TreeNode* root)
{
if (root == 0)
return;
stack<TreeNode> s;
s.push(root);
cout << root->val << ' '; // visit root
TreeNode last_pop = root;
while (!s.empty())
{
TreeNode* top = s.top();
if (top->left != 0 && top->left != last_pop && top->right != last_pop) // push_left
{
s.push(top->left);
cout << top->left->val << ' '; // visit top->left
}
else if (top->right != 0 && top->right != last_pop && (top->left == 0 || top->left == last_pop)) // push_right
{
s.push(top->right);
cout << top->right->val << ' '; // visit top->right
}
else // pop
{
s.pop();
last_pop = top;
}
}
} -
inorder
void inorder_traversal_iteratively(TreeNode* root)
{
if (root == 0)
return;
stack<TreeNode> s;
s.push(root);
TreeNode last_pop = root;
while (!s.empty())
{
TreeNode* top = s.top();
if (top->left != 0 && top->left != last_pop && top->right != last_pop) // push_left
{
s.push(top->left);
}
else if (top->right != 0 && top->right != last_pop && (top->left == 0 || top->left == last_pop)) // push_right
{
s.push(top->right);
cout << top->val << ' '; // visit top
}
else // pop
{
s.pop();
last_pop = top;
if (top->right == 0)
cout << top->val << ' '; // visit top
}
}
} -
postorder
void postorder_traversal_iteratively(TreeNode* root)
{
if (root == 0)
return;
stack<TreeNode> s;
s.push(root);
TreeNode last_pop = root;
while (!s.empty())
{
TreeNode* top = s.top();
if (top->left != 0 && top->left != last_pop && top->right != last_pop) // push_left
{
s.push(top->left);
}
else if (top->right != 0 && top->right != last_pop && (top->left == 0 || top->left == last_pop)) // push_right
{
s.push(top->right);
}
else // pop
{
s.pop();
last_pop = top;
cout << top->val << ' '; // visit top
}
}
}
3.prev记录方法 - 九章算法里的postorder做法：
//Iterative
public ArrayList<Integer> postorderTraversal(TreeNode root) {
ArrayList<Integer> result = new ArrayList<Integer>();
Stack<TreeNode> stack = new Stack<TreeNode>();
TreeNode prev = null; // previously traversed node
TreeNode curr = root;
if (root == null) {
return result;
}
stack.push(root);
while (!stack.empty()) {
curr = stack.peek();
if (prev == null || prev.left == curr || prev.right == curr) { // traverse down the tree
if (curr.left != null) {
stack.push(curr.left);
} else if (curr.right != null) {
stack.push(curr.right);
}
} else if (curr.left == prev) { // traverse up the tree from the left
if (curr.right != null) {
stack.push(curr.right);
}
} else { // traverse up the tree from the right
result.add(curr.val);
stack.pop();
}
prev = curr;
}
return result;
}
4.用两个栈实现后序遍历的方法：
设置两个栈stk, stk2；
将根结点压入第一个栈stk；
弹出stk栈顶的结点，并把该结点压入第二个栈stk2；
将当前结点的左孩子和右孩子先后分别入栈stk；
当所有元素都压入stk2后，依次弹出stk2的栈顶结点，并访问之。
第一个栈的入栈顺序是：根结点，左孩子和右孩子；于是，压入第二个栈的顺序是：根结点，右孩子和左孩子。因此，弹出的顺序就是：左孩子，右孩子和根结点。
void postOrder2(TreeNode *root) {
if(root == NULL)
return;
stack<TreeNode *> stk, stk2;
stk.push(root);
while(!stk.empty()) {
TreeNode *pNode = stk.top();
stk.pop();
stk2.push(pNode);
if(pNode->left != NULL)
stk.push(pNode->left);
if(pNode->right != NULL)
stk.push(pNode->right);
}
while(!stk2.empty()) {
cout << stk2.top()->val << endl;
stk2.pop();
}
}
