1. 题目
给定一个二叉树的根节点
root，返回 它的 中序 遍历
2. 示例
示例 1：
输入：root = [1,null,2,3]
输出：[1,3,2]
示例 2：
输入：root = []
输出：[]
示例 3：
输入：root = [1]
输出：[1]
3. 分析
1.左子树访问完毕后，才能访问根
2.左树节点先不访问，不为空时就入栈
3.和二叉树的前序遍历不一样的地方在于，入数组的时机不一样：
（1） 前序是入栈时就入数组
（2）中序是出栈时就入数组
4. 代码实现
1. /** 2. * Definition for a binary tree node. 3. * struct TreeNode { 4. * int val; 5. * TreeNode *left; 6. * TreeNode *right; 7. * TreeNode() : val(0), left(nullptr), right(nullptr) {} 8. * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} 9. * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} 10. * }; 11. */ 12. class Solution { 13. public: 14. vector<int> inorderTraversal(TreeNode* root) { 15. stack<TreeNode*> st; 16. vector<int> ret; 17. TreeNode* cur = root; 18. 19. //循环开始，cur指向哪个节点，就表示中序访问这棵树 20. //1.左路节点入栈 21. while(cur || !st.empty()) 22. { 23. while(cur) 24. { 25. st.push(cur); 26. cur = cur->left; 27. } 28. 29. //依次取栈中左路节点，这时表示这个节点的左子树已经访问完了 30. //先访问它，再以子问题的形式访问它的右子树 31. TreeNode* top = st.top(); 32. st.pop(); 33. 34. ret.push_back(top->val); 35. 36. //子问题的形式访问这些右子树 37. cur = top->right; 38. } 39. 40. return ret; 41. 42. } 43. };
