94. Binary Tree Inorder Traversal 二叉树的中序遍历

@TOC

# 题目描述

Given a binary tree, return the inorder traversal of its nodes' values.

For example:

``````Given binary tree [1,null,2,3],
1
\
2
/
3
return [1,3,2].
``````

Note: Recursive solution is trivial, could you do it iteratively?

# 解题方法

# 递归

Python代码如下：

``````# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
def inorderTraversal(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
def inorder(root):
if root == None:
return None
if root.left != None:
inorder(root.left)
if root.right != None:
inorder(root.right)
inorder(root)
``````

C++代码如下：

``````/**
* Definition for a binary tree node.
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
inOrder(root);
return res;
}
private:
vector<int> res;
void inOrder(TreeNode* root) {
if (!root) return;
inOrder(root->left);
res.push_back(root->val);
inOrder(root->right);
}
};
``````

# 迭代

Python代码如下。

``````# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
def inorderTraversal(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
stack = []
while True:
while root:
stack.append(root)
root = root.left
if not stack:
root = stack.pop()
root = root.right
``````

C++代码如下：

``````/**
* Definition for a binary tree node.
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
stack<TreeNode*> s;
vector<int> res;
TreeNode* p = root;
while (!s.empty() || p) {
if (p) {
s.push(p);
p = p->left;
} else {
TreeNode* t = s.top(); s.pop();
res.push_back(t->val);
p = t->right;
}
}
return res;
}
};
``````

# 日期

2018 年 2 月 8 日 2018 年 12 月 11 日 —— 双十一已经过去一个月了，真快啊。。