力扣 LeetCode 94. 二叉树的中序遍历（Day6：二叉树）

解题思路：

方法一：递归（左中右）

class Solution {List<Integer> res = new ArrayList<>();public List<Integer> inorderTraversal(TreeNode root) {recur(root);return res;}public void recur(TreeNode root) {if (root == null) return;recur(root.left);res.add(root.val);recur(root.right);}
}

方法二：迭代（非递归法）

前中后序迭代法都是使用栈

前序和后序使用类似的方法

中序方法不同与前序和后序，需要单独区分

 cur != null 时，首先 cur = cur.left 遍历到底进行栈push

为空时，回到上一个不为空的位置并弹出该值，继续 cur = cur.left 遍历该值右边的位置

注意while循环条件

class Solution {public List<Integer> inorderTraversal(TreeNode root) {Deque<TreeNode> stack = new ArrayDeque<>();List<Integer> res = new ArrayList<>();if (root == null) return res;TreeNode cur = root;while (cur != null || !stack.isEmpty()) {if (cur != null) {stack.push(cur);cur = cur.left;} else {cur = stack.pop();res.add(cur.val);cur = cur.right;}}return res;}
}