94 二叉树的中序遍历

解题思路：
\qquad 首先理解中序遍历：left node——root——right node。
\qquad 中序遍历的起始点为该树最左边的非空元素。本题可以使用递归、DFS（迭代）解决。

递归法：
\qquad 重复的基础操作：输出root左边的所有节点，输出root的值，输出root右边的所有节点

	vector<int> inorderTraversal(TreeNode* root) {       vector<int> v;       inOrder(root, v);       return v;     }      void inOrder(TreeNode* root, vector<int>& vec)     {         if(!root) return;         inOrder(root->left, vec);         vec.push_back(root->val);         inOrder(root->right, vec);     } 

迭代法：
\qquad 利用栈，对二叉树进行深度优先搜索，按照“左 — 中 — 右”的方式输出。在此回顾一下C++ STL 栈(stack) 的用法:

vector<int> inorderTraversal(TreeNode* root) {       vector<int> v;       stack<TreeNode*> stk;       while((root != nullptr) || !stk.empty())       {         while(root)         {             stk.push(root);             root = root->left;         }         root = stk.top();         v.push_back(root->val);         stk.pop();         root = root->right;       }       return v;     }