题目描述
输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6},则重建二叉树并输出它的后序遍历序列。(测试用例中,"树"的输出形式类似于树的层次遍历,没有节点的用#来代替)
/** * Definition for binary tree * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class Solution { public TreeNode reConstructBinaryTree(int [] pre, int [] in) { if (pre==null || in==null || in.length<=0) { return null; } return ConstructCore(pre, 0, in.length-1, in, 0, in.length-1); } public static TreeNode ConstructCore(int[] preOrder, int startPreIndex, int endPreIndex, int[] inOrder, int startInIndex, int endInIndex) { int rootValue = preOrder[startPreIndex]; TreeNode root = new TreeNode(rootValue); if (startPreIndex == endPreIndex) { if (startInIndex == endInIndex && preOrder[startPreIndex] == inOrder[startInIndex]) { return root; } } int rootInIndex = startInIndex; while (rootInIndex <= endInIndex && inOrder[rootInIndex] != rootValue) { ++rootInIndex; } int leftLength = rootInIndex - startInIndex; int leftPreOrderEndIndex = startPreIndex + leftLength; if (leftLength > 0) { root.left = ConstructCore(preOrder, startPreIndex + 1, leftPreOrderEndIndex, inOrder, startInIndex, rootInIndex - 1); } if (leftLength < endPreIndex - startPreIndex) { root.right = ConstructCore(preOrder, leftPreOrderEndIndex + 1, endPreIndex, inOrder, rootInIndex + 1, endInIndex); } return root; } }
相关推荐
前序和中序重建二叉树并包含父节点
python 四种方法解析重建二叉树,七种方法遍历二叉树 四种方法解析重建二叉树包括: 1、通过对象实例的左右儿子方法重建 2、通过键盘输入先序遍历重建 3、通过先序遍历的列表重建 4、通过层序遍历列表重建 七种方法...
重建二叉树.md
剑指offer面试题(7)——重建二叉树整体工程代码,C++语言实现。
题目描述: 输入某二叉树的前序遍历...例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6},则重建二叉树并返回。 解题思路参考:https://blog.csdn.net/flower_48237/article/details/104045941
剑指Offer(Python多种思路实现):重建二叉树 面试7题: 题目:输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,...
本文实例讲述了Python实现重建二叉树的三种方法。分享给大家供大家参考,具体如下: 学习算法中,探寻重建二叉树的方法: 用input 前序遍历顺序输入字符重建 前序遍历顺序字符串递归解析重建 前序遍历顺序字符串...
例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6},则重建二叉树并返回。 什么是二叉树? 二叉树(Binary Tree)是n(n≥0)个节点的有限集合,它或者是空集(n=0),或者是由一个根节点以及...
【Python学习-二叉树-递归】【剑指offer】之重建二叉树题目基础知识例子思路分析递归代码 题目 输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字...
例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6},则重建二叉树并返回。* Definition for a
重建二叉树1
本文实例讲述了Python利用前序和中序遍历结果重建二叉树的方法。分享给大家供大家参考,具体如下: 题目:输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含...
本文实例讲述了C++基于先序、中序遍历结果重建二叉树的方法。分享给大家供大家参考,具体如下: 题目: 输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含...
解题思路首先明确什么是前序遍历和中序遍历以及后序遍历,所谓的前、中、后序遍历描述的都是根(中间)节点的遍历顺序,比如:前序遍历结果是:1、2、4、5、3、6、7
# Python实现《剑指offer》 部分代码自己添加了一些测试用例, 或者自己添加了一些功能 1. 初级程序员注重算法和数据结构 2. 事先做好准备,对工作有热情 3. 面试过程放松。不要急于写代码,了解清楚所要解决的问题,...
1.前序遍历结果应该是: 1.假设我们知道了某颗子树根结点(的值),需要查找它在中序遍历中的位置,因为乜有重复数字所以可以遍历整个中序序列,但时间复杂度是O(N
基于二叉链表的二叉树,实现了二叉树的多种操作:添加、删除、拷贝、清空、树深度计算、父节点、兄弟节点获取、先中后序递归及非遍历、按层次遍历、中序迭代器(非递归算法)、节点查找、先序和中序序列重建二叉树、...
假设前序遍历和中序遍历结果中都不包含重复的数字,例如输入的前序遍历序列 {1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}重建出
(2)采用先序递归遍历左子树 (3)采用先序递归遍历右子树 (1)先访问根节点 A (2)A 分为左右两个子树,因为是递归调用,所以左子树也遵循 “先根节点 -