There are three types of depth-first traversal: pre-order,in-order, and post-order.
For a binary tree, they are defined as operations recursively at each node, starting with the root node as follows:
Pre-order
Visit the root.
Traverse the left subtree.
Traverse the right subtree.
iterativePreorder(node)
parentStack = empty stack
parentStack.push(null)
top = node
while ( top != null )
visit( top )
if ( top.right != null )
parentStack.push(top.right)
if ( top.left != null )
parentStack.push(top.left)
top = parentStack.pop()
In-order
Traverse the left subtree.
Visit root.
Traverse the right subtree.
iterativeInorder(node)
parentStack = empty stack
while (not parentStack.isEmpty() or node ≠ null)
if (node ≠ null)
parentStack.push(node)
node = node.left
else
node = parentStack.pop()
visit(node)
node = node.right
Post-order
Traverse the left subtree.
Traverse the right subtree.
Visit the root.
iterativePostorder(node)
parentStack = empty stack
lastnodevisited = null
while (not parentStack.isEmpty() or node ≠ null)
if (node ≠ null)
parentStack.push(node)
node = node.left
else
peeknode = parentStack.peek()
if (peeknode.right ≠ null and lastnodevisited ≠ peeknode.right)
/* if right child exists AND traversing node from left child, move right */
node = peeknode.right
else
parentStack.pop()
visit(peeknode)
lastnodevisited = peeknode
Morris Travel
/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<int> inorderTraversal(TreeNode *root) {
vector<int> ret;
if (!root) return ret;
TreeNode *cur = root; while (cur) {
if (!cur->left) {
ret.push_back(cur->val);
cur = cur->right;
} else {
TreeNode *rightmost = cur->left;
while (rightmost->right != NULL && rightmost->right != cur) rightmost = rightmost->right;
if (rightmost->right == cur) {
rightmost->right = NULL;
ret.push_back(cur->val);
cur = cur->right;
} else {
rightmost->right = cur;
cur = cur->left;
}
}
} return ret;
}
};
后序：
