培训机构图片,网站seo视频,织梦微信网站模板,免费直播网站* 题意说明#xff1a;
* 给定一个二叉树的根节点 root #xff0c;返回 它的 中序 遍历 。
*
* 示例 1#xff1a;
* 输入#xff1a;root [1,null,2,3]
* 输出#xff1a;[1,3,2]
*
* 示例 2#xff1a;
* 输入#xff1a;root []
* 输出#xff1a;[]
*
*…* 题意说明
* 给定一个二叉树的根节点 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 ListInteger 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 ListInteger inorderTraversal(TreeNode root) {ArrayListInteger list new ArrayList();dfs(list,root);return list;}public static void dfs(ListInteger 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;}
}
