题目链接：94. 二叉树的中序遍历（简单）
算法原理：
解法一：递归
0ms击败100.00%
时间复杂度O(N)
思路很简单，就是按照“左根右”的顺序递归即可
下面这篇博客有详细解析👇目录位置：二叉树→二叉树的遍历→中序遍历（递归写法）
Java数据结构——7.二叉树《干货笔记》
解法二：栈
1ms击败21.93%
时间复杂度O(N)
就是再前序遍历回溯到根节点时再顺便存一下
解法一的博客里也有详细解析，目录位置：OJ面试题→二叉树中序非递归遍历
Java代码：
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { //解法一：递归 List<Integer> ret; public List<Integer> inorderTraversal(TreeNode root) { ret=new LinkedList<>(); dfs(root); return ret; } private void dfs(TreeNode node){ if(node==null) return; dfs(node.left); ret.add(node.val); dfs(node.right); } }/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { //解法二：栈 List<Integer> ret; public List<Integer> inorderTraversal(TreeNode root) { ret=new LinkedList<>(); dfs(root); return ret; } private void dfs(TreeNode node){ if(node==null) return; Stack<TreeNode> stack=new Stack<>(); TreeNode cur=node; while(cur!=null||!stack.isEmpty()){ while(cur!=null){ stack.push(cur); cur=cur.left; } TreeNode top=stack.pop(); ret.add(top.val); cur=top.right; } } }
