Binary Tree Inorder Traversal

问题描述：

给定一棵二叉树，返回它的中序遍历。

解题思路：

中序遍历的法则： 遍历左子树 访问当前元素 遍历右子树 根据中序遍历的法则，可以得到相应的算法： 声明一个栈用来存储还没遍历到的节点，而且从栈顶到栈底是向根部回推的一个过程 声明一个遍历指针ptr并赋值为root 对于每个节点        if有左子树                              将该节点压入栈               ptr更新为该节点的左子树        else 无左子树                              访问该节点值                              if有右子树                                            ptr更新为该节点的右子树               else 无右子树（是树叶）                                     如果栈空    则结束                                             while栈不空                                       访问栈顶元素并判断有无右子树                                                          if无右子树   则弹出栈顶元素                                                           else  跳出循环                                             if栈空    则结束                             else      ptr更新为栈顶元素的右子树并弹出栈顶元素                                          

源代码如下：

class Solution {

public:     vector<int> inorderTraversal(TreeNode* root) {         vector<int> result;         stack<TreeNode* > stk;         TreeNode* ptr=root;         if(ptr==NULL) return result;         while(true)         {             if(ptr->left!=NULL)             {                 stk.push(ptr);                 ptr=ptr->left;             }             else if(ptr->right!=NULL)             {                 result.push_back(ptr->val);                 ptr=ptr->right;             }             else             {                 result.push_back(ptr->val);                 if(stk.empty()) break;                 else                 {                        while(!stk.empty())                     {                         result.push_back(stk.top()->val);                         if(stk.top()->right==NULL) stk.pop();                         else break;                     }                     if(stk.empty()) break;                     else                     {                         ptr=stk.top()->right;                         stk.pop();                     }                 }             }         }         return result;     } };