LeetCode 之二叉树中序遍历（使用栈实现）

1、题目描述

2、使用栈实现难度大于使用递归实现

3、代码

 1 vector<int> inorderTraversal(TreeNode* root) {
 2         // 非递归实现，借助栈
 3         vector<int> ans;
 4         if( root == NULL)
 5             return ans;
 6         
 7         stack< const TreeNode *> s;
 8         const TreeNode* p = root;
 9         
10         while( !s.empty()  || p != NULL )
11         {
12             if( p != NULL )
13             {
14                 s.push(p);
15                 p = p->left;
16             }
17             else
18             {
19                 p = s.top();
20                 s.pop();
21                 ans.push_back( p->val );
22                 p = p->right;
23             }
24             
25         }
26         
27         return ans;