LeetCode算法系列 94. 二叉树的中序遍历

LeetCode算法系列（Java版） 144. 二叉树的前序遍历
LeetCode算法系列（Java版） 94. 二叉树的中序遍历
LeetCode算法系列（Java版） 145. 二叉树的后序遍历

力扣原题

94. 二叉树的中序遍历

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

示例 1：

输入：root = [1,null,2,3]
输出：[1,3,2]

示例 2：

输入：root = []
输出：[]

示例 3：

输入：root = [1]
输出：[1]

示例 4：

输入：root = [1,2]
输出：[2,1]

示例 5：

输入：root = [1,null,2]
输出：[1,2]

二叉树

二叉树是一种「数据结构」，简单来说，就是一个包含节点，以及它的左右孩子的一种数据结构。

遍历方式

如果对每一个节点进行编号，你会用什么方式去遍历每个节点呢？

1. 前序遍历

如果你按照 根节点 -> 左孩子 -> 右孩子 的方式遍历，即「先序遍历」，每次先遍历根节点，遍历结果为 1 2 4 5 3 6 7；

2. 中序遍历

如果你按照 左孩子 -> 根节点 -> 右孩子 的方式遍历，即「中序遍历」，遍历结果为 4 2 5 1 6 3 7；

3. 后序遍历

如果你按照 左孩子 -> 右孩子 -> 根节点 的方式遍历，即「后序遍历」，遍历结果为 4 5 2 6 7 3 1；

4. 层次遍历

「层次遍历」就是按照每一层从左向右的方式进行遍历，遍历结果为 1 2 3 4 5 6 7。

方法一：递归

思路与算法

二叉树的中序遍历：按照访问 左子树——根节点——右子树 的方式遍历这棵树，而在访问左子树或者右子树的时候我们按照同样的方式遍历，直到遍历完整棵树。因此整个遍历过程天然具有递归的性质，我们可以直接用递归函数来模拟这一过程。

定义 inorder(root) 表示当前遍历到 root 节点的答案，那么按照定义，我们只要递归调用 inorder(root.left) 来遍历 root 节点的左子树，然后将 root 节点的值加入答案，再递归调用inorder(root.right) 来遍历 root 节点的右子树即可，递归终止的条件为碰到空节点。

代码实现

class Solution {

    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();
        inorder(root, res);
        return res;
    }

    public void inorder(TreeNode root, List<Integer> res) {
        if (root == null) {
            return;
        }
        inorder(root.left, res);
        res.add(root.val);
        inorder(root.right, res);
    }
}

复杂度分析

时间复杂度：，其中为二叉树节点的个数。二叉树的遍历中每个节点会被访问一次且只会被访问一次。
空间复杂度：，空间复杂度取决于递归的栈深度，而栈深度在二叉树为一条链的情况下会达到的级别。

方法二：迭代

思路与算法

同理创建一个 Stack，然后按 左中右 的顺序输出节点。
尽可能的将这个节点的左子树压入 Stack，此时栈顶的元素是最左侧的元素，其目的是找到一个最小单位的子树( 也就是最左侧的一个节点 )，并且在寻找的过程中记录了来源，才能返回上层，同时在返回上层的时候已经处理完毕左子树了。
当处理完最小单位的子树时，返回到上层处理了中间节点。（如果把整个左中右的遍历都理解成子树的话，就是处理完 左子树->中间(就是一个节点)->右子树 ）
如果有右节点，其也要进行中序遍历。

当整个左子树退栈的时候这个时候输出了该子树的根节点 2，之后输出中间节点 1。然后处理根节点为3右子树。

代码实现

public static void inOrderIteration(TreeNode head) {
 if (head == null) {
  return;
 }
 TreeNode cur = head;
 Stack<TreeNode> stack = new Stack<>();
 while (!stack.isEmpty() || cur != null) {
  while (cur != null) {
   stack.push(cur);
   cur = cur.left;
  }
  TreeNode node = stack.pop();
  System.out.print(node.value + " ");
  if (node.right != null) {
   cur = node.right;
  }
 }
}