Leetcode #94 Binary Tree Inorder Traversal

 1 class Solution
 2 {
 3 public:
 4     vector<int> inorderTraversal(TreeNode *root)
 5     {
 6         vector<int> output;
 7         if(root == NULL)
 8         {
 9             return output;
10         }
11 
12         stack<TreeNode*> nodeStack;
13 
14         while(root != NULL || !nodeStack.empty())
15         {
16             if(root != NULL)
17             {
18                 nodeStack.push(root);
19                 root = root->left; //找到最左边的叶子节点。
20             }
21             else
22             {
23                 root = nodeStack.top(); //回退一个节点。
24                 nodeStack.pop();
25                 output.push_back(root->val); //输出当前节点。
26                 root = root->right; //进入右子树。当前节点并没有再次入栈，也就是说，下次回退的时候，会退到当前节点的父节点，从而避免了重复打印。
27             }
28         }
29 
30         return output;
31     }
32 };