A.每日一题——94. 二叉树的中序遍历

题目链接：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; } } }