1.问题
给定一个二叉树的根节点 root ,返回 它的 中序 遍历 。
示例 1

图1
输入:root = [1,null,2,3]
输出:[1,3,2]
示例 2
输入:root = []
输出:[]
示例 3
输入:root = [1]
输出:[1]
提示:
- 树中节点数目在范围 [0, 100] 内
- -100 <= Node.val <= 100
2.解题思路
2.1 递归
类似【LeetCode】144.二叉树的前序遍历,中序遍历规则为 左-根-右,只要对前序遍历-递归稍作调整,即可实现;
复杂度分析
时间复杂度:O(n),其中 n 为二叉树节点的个数。二叉树的遍历中每个节点会被访问一次且只会被访问一次。
空间复杂度:O(n)。空间复杂度取决于递归的栈深度,而栈深度在二叉树为一条链的情况下会达到 O(n) 的级别。
2.2 迭代(栈)
若利用栈(迭代思想),则需要调整下入栈顺序,遍历顺序
1)先遍历根节点,入栈
图2
2)循环遍历左子树

图3

图4
3)到达最左边,出栈,遍历该节点右子树,入栈,没有的话,再出栈该节点的根节点,比如目前节点是4,右子树没有了,出栈根节点2

图5

图6

图7

图8
4)根节点的左子树遍历完毕,开始遍历1的右子树,先出栈根节点1,同理遍历右子树
图9

图10

图11

图12

图13

图14
复杂度分析
时间复杂度:O(n),其中 n 为二叉树节点的个数。二叉树的遍历中每个节点会被访问一次且只会被访问一次。
空间复杂度:O(n)。空间复杂度取决于栈深度,而栈深度在二叉树为一条链的情况下会达到 O(n) 的级别。
3.代码
/* * public class TreeNode { * int val = 0; * TreeNode left = null; * TreeNode right = null; * public TreeNode(int val) { * this.val = val; * } * } */ public class Solution { /** * 递归 * * 递归算法 * @param root TreeNode类 * @return int整型一维数组 */ public int[] inorderTraversal2 (TreeNode root) { if (null == root) { return new int[0]; } List<Integer> list = new ArrayList(); inorderTraversal2(list, root); return list.stream().mapToInt(Integer::valueOf).toArray(); } public void inorderTraversal2 (List<Integer> list, TreeNode root) { if (null == root) { return; } inorderTraversal2(list, root.left); list.add(root.val); inorderTraversal2(list, root.right); } /** 非递归算法 */ public int[] inorderTraversal (TreeNode root) { if (root == null) { return new int[0]; } List<Integer> list = new ArrayList<>(); TreeNode cur = root; Stack<TreeNode> stack = new Stack<>(); TreeNode top = null; while (cur != null || !stack.isEmpty()) { //把左节点所有左节点入栈 while (cur != null) { stack.push(cur); cur = cur.left; } //出栈 top = stack.pop(); list.add(top.val); cur = top.right; } int size = list.size(); int[] arr = new int[size]; for (int i = 0; i < size; i++) { arr[i] = list.get(i); } return arr; } }