【每日一题】LeetCode 94.二叉树的中序遍历（栈、树、深度优先搜索、二叉树）

【每日一题】LeetCode 94.二叉树的中序遍历（栈、树、深度优先搜索、二叉树）

题目描述

给定一个二叉树的根节点 root，返回它的中序遍历结果。中序遍历的顺序是先遍历左子树，然后访问根节点，最后遍历右子树。

思路分析

中序遍历是一种深度优先搜索算法，其遍历顺序遵循左-根-右的规则。对于二叉树的中序遍历，我们可以采用递归的方法来实现：

1. 递归到最左侧：首先递归遍历左子树，直到达到最左侧的节点。
2. 访问节点：访问当前节点，将其值添加到结果列表中。
3. 递归到最右侧：接着递归遍历右子树。

递归的基本情况是，如果当前节点为空，则直接返回。

输入示例

• 示例 1：

  • 输入：root = [1,null,2,3]
  • 输出：[1,3,2]
    

• 示例 2：

  • 输入：root = []
  • 输出：[]

• 示例 3：

  • 输入：root = [1]
  • 输出：[1]

代码实现

import java.util.ArrayList;
import java.util.List;/*** 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 {/*** 返回二叉树的中序遍历结果* @param root 树的根节点* @return 中序遍历的列表*/public List<Integer> inorderTraversal(TreeNode root) {List<Integer> list = new ArrayList<>();dfs(root, list);return list;}/*** 递归进行中序遍历* @param root 当前节点* @param list 存储遍历结果的列表*/public void dfs(TreeNode root, List<Integer> list) {// 如果当前节点为空，直接返回if (root == null) {return;}// 递归遍历左子树dfs(root.left, list);// 访问当前节点，将其值添加到列表中list.add(root.val);// 递归遍历右子树dfs(root.right, list);}
}