94 二叉树的中序遍历

一、题目

给定一个二叉树的根节点 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) {

        // 创建一个空的列表 res，用于按顺序收集和存放遍历到的节点值
        List<Integer> res = new ArrayList<Integer>();

        // 调用我们自己编写的辅助函数 inorder，开始从根节点执行真正的遍历工作
        inorder(root, res);

        // 递归结束后，所有的节点值都已经按“中序”装入 res 中，直接返回即可
        return res;
    }

    // 【辅助函数：执行实际的递归遍历逻辑】
    // 每次调用这个函数，你可以把它想象成“派一个小机器人去考察当前节点 root”
    public void inorder(TreeNode root, List<Integer> res) {

        // 【递归的终止条件 / 边界情况】（这是所有递归代码的灵魂）
        // 如果当前考察的节点是空的（说明这条路已经走到尽头，或者一开始就是一棵空树）
        // 机器人无事可做，直接原路返回 (return)
        if(root == null) {
            return;
        }

        // 【步骤 1：一头扎进左子树】
        // 按照“左->根->右”的原则，先不要管当前节点 root 的值是多少。
        // 派机器人继续往左下方探索，直到把左边的分支全部处理完毕。
        inorder(root.left, res);

        // 【步骤 2：处理当前节点（根节点）】
        // 代码能执行到这一行，说明当前节点的所有左边子孙都已经被妥善处理完了（或者它根本就没有左孩子）。
        // 现在，终于轮到当前节点了，把它的值加入到结果列表中。
        res.add(root.val);

        // 【步骤 3：再去探索右子树】
        // 当前节点也处理完了，最后再派机器人以同样的规则，去右下方探索。
        inorder(root.right, res);
    }
}

时间复杂度：O(n)O(n)

空间复杂度：O(h)O(h)

评论