思路

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

解法

  1. class Solution {
  2.     public List<Integer> inorderTraversal(TreeNode root) {
  3.         List<Integer> res = new ArrayList<Integer>();
  4.         inorder(root, res);
  5.         return res;
  6.     }
  8.     public void inorder(TreeNode root, List<Integer> res){
  9.         if(root == null){
  10.             return;
  11.         }
  12.         inorder(root.left, res);
  13.         res.add(root.val);
  14.         inorder(root.right, res);
  15.     }
  16. }
  • 时间复杂度：leetcode-94：二叉树的中序遍历 - 图1，其中 n 为二叉树节点的个数。二叉树的遍历中每个节点会被访问一次且只会被访问一次
  • 空间复杂度：leetcode-94：二叉树的中序遍历 - 图2，空间复杂度取决于递归的栈深度，而栈深度在二叉树为一条链的情况下会达到leetcode-94：二叉树的中序遍历 - 图3的级别