有没有专做推广小说的网站,ui设计是什么时候开始的,2022八月热点新闻摘抄,电商网站排行一般情况下#xff0c;我们会根据先序和后序写出二叉树#xff0c;但是用代码怎末写呢#xff1f;
例如#xff1a;
给定两个整数数组 preorder 和 inorder #xff0c;其中 preorder 是二叉树的先序遍历#xff0c; inorder 是同一棵树的中序遍历#xff0c;请构造二…一般情况下我们会根据先序和后序写出二叉树但是用代码怎末写呢
例如
给定两个整数数组 preorder 和 inorder 其中 preorder 是二叉树的先序遍历 inorder 是同一棵树的中序遍历请构造二叉树并返回其根节点。
思路我们先根据先序遍历找到根节点记录下来在从中序数组中找到刚才记录下来根节点的下标那么下标的左边就是根节点的左子树后边就是根的右子树依次递归求二叉树递归截止条件在下图中说明
开始状态
描述
第一步rootindex是根节点begin和end是根节点的左右子树在中序数组的下标范围下一步你们就明白了 第二步我们找左子树endrootindex-1;begin不动 第三步我们找右子树end不动beginrootindex1; 依次递归每次都是先找根节点再找左子树后右子树结束条件见就是beginend的时候解释相当于该节点是叶子节点 代码展示 public int preindex;//记录先序遍历的下标如果放在递归的方法中递归后值发生改变public TreeNode buildTree(int[] preorder, int[] inorder) {return creatTree(0,inorder.length-1, preorder, inorder);}public TreeNode creatTree(int begin,int end,int [] preorder,int[] inorder){if (beginend)return null;TreeNode root new TreeNode(preorder[preindex]);int rootindexfind(begin, end, preorder[preindex], inorder);//获取根节点在中序数组中下标preindex;root.leftcreatTree( begin, rootindex-1, preorder, inorder);root.rightcreatTree( rootindex1, end, preorder, inorder);return root;}public int find(int begin,int end,int key,int[] inorder){for (int i begin; i end ; i) {if (inorder[i]key)return i;}return -1;}
