## Monday, November 25, 2013

### [LeetCode] Binary Tree Preorder Traversal, Solution

Given a binary tree, return the preorder traversal of its nodes' values.
For example:
Given binary tree `{1,#,2,3}`,
```   1
\
2
/
3```

return `[1,2,3]`.
Note: Recursive solution is trivial, could you do it iteratively?
[Thoughts]
PreOrder:
1. visit node
2. visit node->left
3. visit node->right

function preorder(root)

if root == NULL return;
print root;
preoder(node->left);
preOrder(node->right);

[Code]

``````1:  vector<int> preorderTraversal(TreeNode *root) {
2:       stack<TreeNode*> tStack;
3:       vector<int> result;
4:       while(tStack.size()>0 || root != NULL)
5:       {
6:            if(root != NULL)
7:            {
8:                 result.push_back(root->val);
9:                 if(root->right !=NULL)
10:                 tStack.push(root->right);
11:                 root = root->left;
12:            }
13:            else
14:            {
15:                 root = tStack.top();
16:                 tStack.pop();
17:            }
18:       }
19:       return result;
20:  }
``````

Update 08/20/2014. Another way to use stack

``````1:       vector<int> preorderTraversal(TreeNode *root) {
2:            stack<TreeNode*> stack;
3:            vector<int> result;
4:            TreeNode* cur = root;
5:            while(cur != NULL || stack.size() != 0)
6:            {
7:                 while(cur != NULL)
8:                 {
9:                      result.push_back(cur->val);
10:                      stack.push(cur);
11:                      cur = cur->left;
12:                 }
13:                 cur = stack.top();
14:                 stack.pop();
15:                 cur = cur->right;
16:            }
17:            return result;
18:       }
``````