[面试真题] LeetCode：Binary Tree Inorder Traversal

Given a binary tree, return the inorder traversal of its nodes' values.

Note: Recursive solution is trivial, could you do it iteratively?

二叉树中序遍历，非递归解法。使用栈记录中序遍历时中间节点的访问顺序，从栈中弹出的顺序即为中序。

Program Runtime: 16 milli secs

 1 /**
 2  * Definition for binary tree
 3  * struct TreeNode {
 4  *     int val;
 5  *     TreeNode *left;
 6  *     TreeNode *right;
 7  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 8  * };
 9  */
10 class Solution {
11 public:
12     vector<int> inorderTraversal(TreeNode *root) {
13         // Start typing your C/C++ solution below
14         // DO NOT write int main() function
15         vector<int> rtn;
16         if(root){
17             stack<TreeNode*> s;
18             s.push(root);
19             TreeNode *p = root;
20             while(p->left){
21                s.push(p->left);
22               p = p->left;
23              }
24             while(s.size()){
25                 TreeNode *cur = s.top();
26                 s.pop();
27                 rtn.push_back(cur->val);
28                 if(cur->right){
29                     s.push(cur->right);
30                     cur = cur->right;
31                     while(cur->left){
32                         s.push(cur->left);
33                         cur = cur->left;
34                     }
35                 }
36             }
37         }
38         return rtn;
39     }
40 };