题目：
给定一个二叉树，返回它的中序 遍历。
Given a binary tree, return the inorder traversal of its nodes' values.
示例:
输入: [1,null,2,3]
1
\
2
/
3
输出: [1,3,2]进阶: 递归算法很简单，你可以通过迭代算法完成吗？
Follow up: Recursive solution is trivial, could you do it iteratively?
解题思路：
百度百科：二叉树的中序遍历：https://baike.baidu.com/item/中序遍历
遍历顺序：左子节点 --> 根节点 --> 右子节点
如下所示的二叉树：
A
/ \
B C
/ \ / \
D E F G其遍历顺序为：D -> B -> E -> A ->F -> C -> G
二叉树遍历可以用 DFS（深度优先搜索）完成，其实现方式为：递归或借助数据结构 栈 迭代。
这种遍历方式本质上是一个先进后出的栈式遍历方式，递归方法实际也是用递归方式实现栈的先进后出。
DFS-递归：
Java：
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();//数组
dfs_recursion(root, list);//传入递归函数
return list;
}
private void dfs_recursion(TreeNode node, List<Integer> list) {
if (node == null) return;//基线条件
dfs_recursion(node.left, list);//先遍历左子节点
list.add(node.val);//遍历到左子节点的顶点，取出该节点的值
dfs_recursion(node.right, list);//递归遍历右节点
}
}Python3:
class Solution:
def inorderTraversal(self, root: TreeNode) -> List[int]:
#数组
res = list()
#传入递归函数
self.dfs_recursion(root, res)
return res
def dfs_recursion(self, node: TreeNode, res: List[int]):
#基线条件
if not node: return
#递归遍历左子节点
self.dfs_recursion(node.left, res)
#取顶点节点的值
res.append(node.val)
#递归遍历右子节点
self.dfs_recursion(node.right, res)DFS-迭代：
Java：
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();//数组
if (root == null) return list;
Stack<TreeNode> stack = new Stack<>();//用数据结构栈暂存节点
TreeNode cur = root;//定义当前节点
while (!stack.isEmpty() || cur != null) {//循环条件：栈不空或当前节点不空
if (cur != null) {//当前节点不空时
stack.push(cur);//当前节点入栈
cur = cur.left;//刷新当前节点
} else {//当前节点空时
cur = stack.pop();//当前节点的父节点出栈
list.add(cur.val);//数组存入节点的值
cur = cur.right;刷新当前节点
}
}
return list;
}
}Python:
class Solution:
def inorderTraversal(self, root: TreeNode) -> List[int]:
#初始化数组、栈
res, stack = list(), list()
#当前节点指向根节点
cur = root
#递归条件为：栈或当前节点非空
while stack or cur:
if cur:
#当前节点非空时入栈
stack.append(cur)
#刷新当前节点
cur = cur.left
else:
#当前节点为空时其父节点出栈
cur = stack.pop()
#其值存入数组
res.append(cur.val)
#刷新当前节点
cur =cur.right
return res一起学习吖，欢迎关注：爱写Bug
