【力扣热题100】[Java版] 刷题笔记-94.二叉树的中序遍历

题目：94. 二叉树的中序遍历

给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。

解题思路

首先了解什么是二叉树的中序遍历，中序遍历是首先遍历二叉树的左子树，然后访问根结点，最后遍历右子树。层层遍历得到最终结果。二叉树遍历最简单的方法就是递归，根据题目编写递归的规则，有些题目还可以进行迭代，这个题目正好是递归和迭代都可以进行的。

解题过程

递归：创建数组，按左，根，右的顺序存入列表中。

/*** 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 {public void inorder(TreeNode root,List<Integer> res) {if(root ==null) {return;}// 中序遍历： 左 根 右inorder(root.left,res);res.add(root.val);inorder(root.right,res);}public List<Integer> inorderTraversal(TreeNode root) {List<Integer> res = new ArrayList();if (root == null) {return res;}inorder(root,res);return res;}
}

迭代：利用队列的特性，先进先出，后进后出，遍历查询到二叉树的最后一个左节点，将所有左节点存入队列中，队列逐个删除返回节点，讲节点值存入列表中。

有关队列的讲解可以看我的另一篇文章Java 中的 队列（Queue）与双端队列（Deque）-CSDN博客 

/*** 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 {public List<Integer> inorderTraversal(TreeNode root) {List<Integer> res = new ArrayList();if (root == null) {return res;}Deque<TreeNode> deque = new LinkedList<TreeNode>();while (root != null || !deque.isEmpty()){// 获取到最后的左节点while(root !=null) {deque.push(root);root = root.left;}// 删除并返回第一个元素，即最后一层的左节点root = deque.pop();res.add(root.val);root = root.right;}return res;}
}