【LeetCode】94.二叉树的中序遍历

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;
      }
  }