Given a binary tree, return the inorder traversal of its nodes‘ values.
Example:
Input: [1,null,2,3]
1
2
/
3
Output: [1,3,2]
Follow up: Recursive solution is trivial, could you do it iteratively?
题目要求将二叉树进行中序遍历（inorder）。先来介绍二叉树的三种遍历方式：前序遍历 preorder、中序遍历 inorder和后序遍历 postorder
遍历顺序如下：
前序遍历：根结点->左子树->右子树
中序遍历：左子树->根结点->右子树
后序遍历：左子树->右子树->根结点
由此可以理解题目例子，先遍历左子树，为空，然后是根结点1，然后遍历右子树，右子树同样以先左子树，然后根结点，最后右子树的顺序。因此得到结果[1,3,2]。
方法一：递归法。
整个二叉树的遍历可以分成单个子树遍历后再组合的形式，因此使用递归能很好地解决问题。
代码如下：
class Solution { public: vector<int> inorderTraversal(TreeNode* root) { if (!root)return {}; vector<int> res; vector<int> left = inorderTraversal(root->left); for (int i = 0; i < left.size(); ++i) { res.push_back(left[i]); } res.push_back(root->val); vector<int> right = inorderTraversal(root->right); for (int i = 0; i < right.size(); ++i) { res.push_back(right[i]); } return res; } };
方法二：非递归法。
非递归的方法，借助堆储存根结点。不断找寻一个根结点的左子树，直到没有左子树为止。然后将当前的结点的值放入结果数组res中，然后对右子树用相同的方法遍历。
代码如下：
class Solution { public: vector<int> inorderTraversal(TreeNode* root) { if(!root)return {}; vector<int> res; stack<TreeNode*> s; TreeNode* cur=root; while(cur || !s.empty()){ while(cur){ s.push(cur); cur=cur->left; } cur=s.top(); s.pop(); res.push_back(cur->val); cur=cur->right; } return res; } };
参考：
二叉树遍历：https://www.cnblogs.com/llguanli/p/7363657.html
[LeetCode] 94. Binary Tree Inorder Traversal
原文：https://www.cnblogs.com/cff2121/p/10869441.html