给定两个整数数组 preorder 和 inorder ,表示一个二叉树的前序遍历和中序遍历,重构出原二叉树。假设二叉树的节点值没有重复,二叉树节点的定义已经给出。-笔试面试资料
这是qklbishe.com第6543 篇笔试面试资料
提供答案分析,通过本文《给定两个整数数组 preorder 和 inorder ,表示一个二叉树的前序遍历和中序遍历,重构出原二叉树。假设二叉树的节点值没有重复,二叉树节点的定义已经给出。-笔试面试资料》可以理解其中的代码原理,这是一篇很好的求职学习资料
本站提供程序员计算机面试经验学习,笔试经验,包括字节跳动/头条,腾讯,阿里,美团,滴滴出行,网易,百度,京东,小米,华为,微软等互联网大厂真题学习背诵。
答案:
给定两个整数数组preorder和inorder,表示一个二叉树的前序遍历和中序遍历,重构出原二叉树。假设二叉树的节点值没有重复,二叉树节点的定义已经给出。
《剑指offer》原题,先寻找先序遍历和中序遍历中根节点的位置,将序列划分为左右子树的序列,然后利用递归的方式重构二叉树。
import java.util.*; /* * public class TreeNode { * int val = 0; * TreeNode left = null; * TreeNode right = null; * } */ public class Solution { /** * 二叉树构造 * @param preorder int整型一维数组 前序遍历 * @param inorder int整型一维数组 中序遍历 * @param length int整型 节点数量 * @return TreeNode类 */ public TreeNode constructTree (int[] preorder, int[] inorder, int length) { // write code here if(preorder.length == 0){ return null; }else if(preorder.length == 1){ return new TreeNode(preorder[0]); }else{ TreeNode tree = new TreeNode(preorder[0]); int idx = indexOfArray(inorder, preorder[0]); // 找到根节点在中序遍历序列中的索引 tree.left = constructTree(Arrays.copyOfRange(preorder, 1, idx + 1), Arrays.copyOfRange(inorder, 0, idx), idx); tree.right = constructTree(Arrays.copyOfRange(preorder, idx + 1, preorder.length), Arrays.copyOfRange(inorder, idx+1, inorder.length), length - idx); return tree; } } public int indexOfArray(int[] array, int target){ for(int i = 0;i < array.length;i++) if(array[i] == target) return i; return -1; } }
2021-02-07 18:18:06 回复(0)
文章部分来自互联网,侵权联系删除
www.qklbishe.com
区块链毕设网(www.qklbishe.com)全网最靠谱的原创区块链毕设代做网站部分资料来自网络,侵权联系删除!资源收费仅为搬运整理打赏费用,用户自愿支付 !
qklbishe.com区块链毕设代做网专注|以太坊fabric-计算机|java|毕业设计|代做平台 » 给定两个整数数组 preorder 和 inorder ,表示一个二叉树的前序遍历和中序遍历,重构出原二叉树。假设二叉树的节点值没有重复,二叉树节点的定义已经给出。-笔试面试资料
qklbishe.com区块链毕设代做网专注|以太坊fabric-计算机|java|毕业设计|代做平台 » 给定两个整数数组 preorder 和 inorder ,表示一个二叉树的前序遍历和中序遍历,重构出原二叉树。假设二叉树的节点值没有重复,二叉树节点的定义已经给出。-笔试面试资料