[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<int> preorderTraversal(TreeNode *root) { vector<int> allNodeValues; preorderTrav(root, allNodeValues); return allNodeValues; } void preorderTrav(TreeNode *root, vector<int> &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<int> preorderTraversal(TreeNode *root) { vector<int> allNodeValues; TreeNode *cur = root; stack<TreeNode*> 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; } };