深圳网站建设公司哪好,北京网站手机站建设公司吗,wordpress登录密码忘,哪里可以做网站推广提示#xff1a;文章写完后#xff0c;目录可以自动生成#xff0c;如何生成可参考右边的帮助文档 前言
提示#xff1a;这里可以添加本文要记录的大概内容#xff1a;
3月5日练习内容 提示#xff1a;以下是本篇文章正文内容#xff0c;下面案例可供参考
一、题目-从… 提示文章写完后目录可以自动生成如何生成可参考右边的帮助文档 前言
提示这里可以添加本文要记录的大概内容
3月5日练习内容 提示以下是本篇文章正文内容下面案例可供参考
一、题目-从前序与中序遍历序列构造二叉树
1.题目描述
给定两个整数数组 preorder 和 inorder 其中 preorder 是二叉树的先序遍历 inorder 是同一棵树的中序遍历请构造二叉树并返回其根节点。
示例 1: 输入: preorder [3,9,20,15,7], inorder [9,3,15,20,7] 输出: [3,9,20,null,null,15,7] 示例 2: 输入: preorder [-1], inorder [-1] 输出: [-1] 来源力扣LeetCode 链接https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。
2.思路与代码
2.1 思路
1.根据传入数组数据创建相对应的集合
2.创建makeTree方法用于递归创建树
3.判断中序遍历的集合是否为空为空则输出null
4.由于前序遍历第一个结点为根结点则提取第一个数创建根结点
5.查找根结点在中序遍历中的位置并将中序遍历数组进行左右子树切分用于递归建树
2.2 代码
代码如下示例
/*** 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 TreeNode buildTree(int[] preorder, int[] inorder) {//创建集合ListInteger preList new ArrayList();ListInteger inList new ArrayList();//将数组元素放入集合for(int i 0;i preorder.length;i ){preList.add(preorder[i]);inList.add(inorder[i]);}return makeTree(preList,inList);}//建树public TreeNode makeTree(ListInteger preList,ListInteger inList){if(inList.size() 0){return null;}//前序遍历第一为数字为根结点int rootVal preList.remove(0);//创建根结点TreeNode root new TreeNode(rootVal);//找根结点在中序遍历的位置int mid inList.indexOf(rootVal);//进行切分并建立左子树与右子树root.left makeTree(preList,inList.subList(0,mid));root.right makeTree(preList,inList.subList(mid 1, inList.size()));return root;}
} 总结
提示这里对文章进行总结
