二叉树的中序遍历

思路与算法

二叉树的遍历方式

• 先序遍历：根 - 左 - 右
• 中序遍历：左 - 根 - 右
• 后序遍历：左 - 右 - 根
• 层序遍历：每一层从左至右

递归实现遍历

• 按照左 - 根 - 右的顺序遍历整个二叉树，在遍历左子树或右子树的时候采用同样的方式遍历，具有天然的递归性，而递归的终止条件就是碰到空节点；

• 定义 inorder(root) 表示当前遍历到 root 节点的答案，那么按照定义，我们只要递归调用 inorder(root.left) 来遍历 root 节点的左子树，然后将 root 节点的值加入答案，再递归调用inorder(root.right) 来遍历 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 List<Integer> inorderTraversal(TreeNode root) {
          ArrayList res = new ArrayList();
          inorder(root,res);
          return res;
      }
  
      public void inorder(TreeNode root, List<Integer> res){
          if(null == root){
              return;
          }
          inorder(root.left, res);
          res.add(root.val);
          inorder(root.right, res);
      }
  }

  复杂度分析

• 时间复杂度：O(n)，其中 n 为二叉树节点的个数。二叉树的遍历中每个节点会被访问一次且只会被访问一次。

• 空间复杂度：O(n)。空间复杂度取决于递归的栈深度，而栈深度在二叉树为一条链的情况下会达到 O(n) 的级别。

来源：力扣（LeetCode）