算法工程题（中序遍历）

*  题意说明：
*  给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。
*
*  示例 1：
*  输入：root = [1,null,2,3]
*  输出：[1,3,2]
*
*  示例 2：
*  输入：root = []
*  输出：[]
*
*  示例 3：
*  输入：root = [1]
*  输出：[1]
*
*  提示：
*  树中节点数目在范围 [0, 100] 内
*  -100 <= Node.val <= 100
*  进阶: 递归算法很简单，你可以通过迭代算法完成吗？
*
*  Related Topics
*  栈
*  树
*  深度优先搜索
*  二叉树
*
* @Date 2023/8/30 10:07
* @Version 1.0
*/

public class InorderTraversal {public static void main(String[] args) {// 测试代码入口}public static List<Integer> inorderTraversal(TreeNode root) {return null;}
}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;}
}

使用递归实现：

public class InorderTraversal {public static void main(String[] args) {// 测试代码入口//创建测试数据 二叉树TreeNode treeNode = new TreeNode();treeNode = new TreeNode(1);treeNode.left = new TreeNode(2);treeNode.right = new TreeNode(3);System.out.println(inorderTraversal(treeNode));}//通过递归的方式来进行实现中序排序public static List<Integer> inorderTraversal(TreeNode root) {ArrayList<Integer> list = new ArrayList<>();dfs(list,root);return list;}public static void dfs(List<Integer> list ,TreeNode root){//如果为null则直接返回if(root  == null){return;}//遍历左子树dfs(list,root.left);//添加根list.add(root.val);//遍历右子树dfs(list,root.right);}
}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;}
}