Leetcode: Binary tree preorder traversal

Note: Recursive solution is trivial, could you do it iteratively?

May 26, 2015 - Read the website:

http://en.wikipedia.org/wiki/Tree_traversal

Read the leetcode solution in C++ first:
class Solution {
public:
vector preorderTraversal(TreeNode *root) {
vector result;
const TreeNode *p;
stack s;
p = root;
if (p != nullptr) s.push(p);
while (!s.empty()) {
p = s.top();
s.pop();
result.push_back(p->val);
if (p->right != nullptr) s.push(p->right);
if (p->left != nullptr) s.push(p->left);
}
return result;
}
};

Here is the C# code:

https://github.com/jianminchen/leetcode-tree/blob/master/TreePreOrderTraversal.cs

Morris preorder:

http://www.geeksforgeeks.org/inorder-tree-traversal-without-recursion-and-without-stack/

original paper (read it if I need to challenge my understanding)

http://www.sciencedirect.com/science/article/pii/0167642388900639

The explanation in the following blog is more clear compared to Leetcode solution.

http://codingrecipies.blogspot.ca/2013/11/morris-inorder-traversal.html

https://plus.google.com/+PrateekRathore/posts

Here is the pseudo code:

preorder(node)
  if node == null then return
  visit(node)
  preorder(node.left) 
  preorder(node.right)

这道题有意思, 考虑到自己很少用栈, 应该好好练习写代码.

iterativePreorder(node)
  parentStack = empty stack
  while (not parentStack.isEmpty() or node ≠ null)
    if (node ≠ null) 
      visit(node)
      if (node.right ≠ null) parentStack.push(node.right) 
      node = node.left   
    else     
      node = parentStack.pop()