Monday, November 10, 2014

[LeetCode] Binary Tree Preorder Traversal

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?

1. 递归解法：

 ``` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15``` ```class Solution { public: vector preorderTraversal(TreeNode *root) { vector allNodeValues; preorderTrav(root, allNodeValues); return allNodeValues; } void preorderTrav(TreeNode *root, vector &allNodeValues) { if(!root) return; allNodeValues.push_back(root->val); preorderTrav(root->left, allNodeValues); preorderTrav(root->right, allNodeValues); } }; ```

2. 迭代解法：

 ``` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20``` ```class Solution { public: vector preorderTraversal(TreeNode *root) { vector allNodeValues; TreeNode *cur = root; stack s; while(cur || !s.empty()) { if(!cur) { cur = s.top(); s.pop(); } allNodeValues.push_back(cur->val); if(cur->right) s.push(cur->right); cur = cur->left; } return allNodeValues; } }; ```