[刷题]LeetCode 144.Binary Tree Preorder Traversal

 1 #include <iostream>
 2 #include <vector>
 3 #include <stack>
 4 #include <cassert>
 5 
 6 using namespace std;
 7 
 8 struct TreeNode{
 9     int val;
10     TreeNode* left;
11     TreeNode* right;
12     TreeNode(int x): val(x), left(NULL), right(NULL){}
13 };
14 
15 //模拟指令，go--访问，print--输出    
16 struct Command{
17     string s;
18     TreeNode* node;
19     Command(string s, TreeNode* node):s(s), node(node){}
20 };
21 
22 class Solution{
23     public:
24         vector<int> preorderTraversal(TreeNode* root){
25             vector<int> res;
26             if( root == NULL )
27                 return res;
28             
29             stack<Command> stack;
30             stack.push( Command("go",root) );
31             
32             while( !stack.empty() ){
33                 
34                 Command command = stack.top();
35                 stack.pop();
36                 
37                 if( command.s == "print" )
38                     res.push_back( command.node -> val);
39                 else{
40                     assert( command.s == "go" );
41                     if( command.node -> right )
42                         stack.push( Command("go",command.node->right));
43                     if( command.node -> left)
44                         stack.push( Command("go",command.node->left));
45                     stack.push( Command("print",command.node));
46                 }
47             }
48         }
49 };
50 
51 void print_vec(const vector<int>& vec){
52     for(int e:vec)
53         cout<<e<<" ";
54     cout<<endl;
55 }
56 
57 int main(){
58     TreeNode* root = new TreeNode(1);
59     root->right = new TreeNode(2);
60     root->right->left = new TreeNode(3);
61     vector<int> res = Solution().preorderTraversal(root);
62     print_vec(res);
63     
64     return 0;
65 }