二叉树的中序遍历

原题链接

使用的方法

递归

解题思路

• 中序遍历的顺序是：左子树 -> 根节点 -> 右子树。
• 递归的核心思想是：对于每个节点，先递归遍历其左子树，然后访问该节点的值，最后递归遍历其右子树。
• 在递归函数中，首先检查当前节点是否为 null，如果是 null，则直接返回，表示已经遍历到叶子节点的下一层了。
• 否则，先递归调用函数遍历左子树，然后将当前节点的值添加到结果列表中，最后递归调用函数遍历右子树。
• 通过这种方式，最终得到的结果列表就是按照中序遍历的顺序存储的节点值。

代码实现

/**
 * 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) {
        List<Integer> res = new ArrayList<>();
        midOrder(root,res);
        return res;
    }
    public void midOrder(TreeNode root,List<Integer> res){
        if(root == null) return; // 检查当前节点是否为null，是则停止递归
        midOrder(root.left,res);
        res.add(root.val);
        midOrder(root.right,res);
    }
}