广州市网站建设制作费用,建设城市2的游戏在哪个网站,大气家具行业商城类公司网站织梦模板,网站着陆页 推荐题目描述 输入某二叉树的前序遍历和中序遍历的结果#xff0c;请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}#xff0c;则重建二叉树并返回。 /// 1/// …题目描述 输入某二叉树的前序遍历和中序遍历的结果请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}则重建二叉树并返回。 /// 1/// / \/// 2 3 /// / / \/// 4 5 6/// \ //// 7 8 解题思路 基础知识 前序遍历根结点 --- 左子树 --- 右子树中序遍历左子树--- 根结点 --- 右子树后序遍历左子树 --- 右子树 --- 根结点层次遍历只需按层次遍历即可 例如 前序遍历1 2 4 7 3 5 6 8中序遍历4 7 2 1 5 3 8 6后序遍历7 4 2 5 8 6 3 1层次遍历1 2 3 4 5 6 7 8 前序遍历首先访问根结点然后遍历左子树最后遍历右子树。在遍历左、右子树时仍然先访问根结点然后遍历左子树最后遍历右子树。中序遍历LDR是二叉树遍历的一种也叫做中根遍历、中序周游。在二叉树中中序遍历首先遍历左子树然后访问根结点最后遍历右子树。二叉树的什么什么遍历其实也是很好记的就是根在呢就是什么遍历在前就是前遍历中就是中序遍历后就是后序遍历其他的是层次遍历。 解题 根据前序遍历可以知道根节点1根据中序遍历可以知道左子树4,7,2和右子树5,3,8,6。找到左右子树之后我们可以以相同的方式找到左右子树也就是说这是一个递归的过程。根左右。 代码实现 二叉树 /// summary/// 二叉树/// /summarypublic class TreeNode{public int val;public TreeNode left;public TreeNode right;public TreeNode(int x){val x;}} 前序遍历根结点 --- 左子树 --- 右子树 public static void PreNode(TreeNode node, Listint treeList){if (node ! null){treeList.Add(node.val);PreNode(node.left, treeList);PreNode(node.right, treeList);}} 中序遍历左子树--- 根结点 --- 右子树 public static void MidNode(TreeNode node, Listint treeList){if (node ! null) {MidNode(node.left, treeList);treeList.Add(node.val);MidNode(node.right, treeList);}} 后序遍历左子树 --- 右子树 --- 根结点 public static void EndNode(TreeNode node, Listint treeList){if (node ! null) {EndNode(node.left, treeList);EndNode(node.right, treeList);treeList.Add(node.val);}} 层次遍历只需按层次遍历即可。思路根据层次遍历的顺序每一层都是从左到右的遍历输出借助于一个队列。先从根节点入队将其出队访问如果当前节点的左节点不为空左节点入队如果当前右节点部位空右节点入队。所以出队顺序是从左到右。 public static void LevelNode(TreeNode node, Listint treeList){if (node ! null) {QueueTreeNode queue new QueueTreeNode();queue.Enqueue(node);TreeNode currentNode null;while (queue.Count 0) {currentNode queue.Dequeue();treeList.Add(currentNode.val);if (currentNode.left ! null) {queue.Enqueue(currentNode.left);}if (currentNode.right ! null) {queue.Enqueue(currentNode.right);}}}} 二叉树的前序遍历和中序遍历的结果请重建出该二叉树。思路根据前序遍历找到根根据中序遍历找到左右子树依次递归。归结根 左 右 public static TreeNode Tree(Listint preTree, Listint midTree){if (preTree null || preTree.Count() 0 || midTree null || midTree.Count() 0){return null;}//根节点int rootTree preTree[0];//移除根节点preTree.RemoveAt(0);TreeNode treeNode new TreeNode(rootTree);//左右子树Listint leftTree null;Listint tempList new Listint();bool isTree false;foreach (var item in midTree){tempList.Add(item);if (item rootTree){isTree true;tempList.Remove(item);leftTree tempList;tempList new Listint();}}if (!isTree) {Console.WriteLine(不是正确的树);return null;}Listint rightTree tempList;//递归左右节点treeNode.left Tree(preTree, leftTree);treeNode.right Tree(preTree, rightTree);return treeNode;} 测试 普通二叉树 /// summary/// 普通二叉树/// 1/// / \/// 2 3 /// / / \/// 4 5 6/// \ //// 7 8 /// /summary[Fact]public void Common() {int[] preTree { 1, 2, 4, 7, 3, 5, 6, 8 };int[] midTree { 4, 7, 2, 1, 5, 3, 8, 6 };TreeNode tree Coding004.Tree(preTree.ToList(), midTree.ToList());Listint result new Listint();Coding004.PreNode(tree, result);Assert.Equal(JsonConvert.SerializeObject(preTree), JsonConvert.SerializeObject(result));result.Clear();Coding004.MidNode(tree, result);Assert.Equal(JsonConvert.SerializeObject(midTree), JsonConvert.SerializeObject(result));} 所有结点都没有右子结点 /// summary/// 所有结点都没有右子结点/// 1/// / /// 2 /// / /// 3 /// /summary[Fact]public void Right(){int[] preTree { 1, 2, 3 };int[] midTree { 3, 2, 1 };TreeNode tree Coding004.Tree(preTree.ToList(), midTree.ToList());Listint result new Listint();Coding004.PreNode(tree, result);Assert.Equal(JsonConvert.SerializeObject(preTree), JsonConvert.SerializeObject(result));result.Clear();Coding004.MidNode(tree, result);Assert.Equal(JsonConvert.SerializeObject(midTree), JsonConvert.SerializeObject(result));} 所有结点都没有左子结点 /// summary/// 所有结点都没有左子结点/// 1/// \ /// 2 /// \ /// 3 /// \////// \/// 5/// /summary[Fact]public void Left(){int[] preTree { 1, 2, 3, 4, 5 };int[] midTree { 1, 2, 3, 4, 5 };TreeNode tree Coding004.Tree(preTree.ToList(), midTree.ToList());Listint result new Listint();Coding004.PreNode(tree, result);Assert.Equal(JsonConvert.SerializeObject(preTree), JsonConvert.SerializeObject(result));result.Clear();Coding004.MidNode(tree, result);Assert.Equal(JsonConvert.SerializeObject(midTree), JsonConvert.SerializeObject(result));} 树中只有一个结点 /// summary/// 树中只有一个结点/// /summary[Fact]public void One(){int[] preTree { 1 };int[] midTree { 1 };TreeNode tree Coding004.Tree(preTree.ToList(), midTree.ToList());Listint result new Listint();Coding004.PreNode(tree, result);Assert.Equal(JsonConvert.SerializeObject(preTree), JsonConvert.SerializeObject(result));result.Clear();Coding004.MidNode(tree, result);Assert.Equal(JsonConvert.SerializeObject(midTree), JsonConvert.SerializeObject(result));} 完全二叉树 /// summary/// 完全二叉树/// 1/// / \/// 2 3 /// / \ / \/// 4 5 6 7/// /summary[Fact]public void All(){int[] preTree { 1, 2, 4, 5, 3, 6, 7 };int[] midTree { 4, 2, 5, 1, 6, 3, 7 };TreeNode tree Coding004.Tree(preTree.ToList(), midTree.ToList());Listint result new Listint();Coding004.PreNode(tree, result);Assert.Equal(JsonConvert.SerializeObject(preTree), JsonConvert.SerializeObject(result));result.Clear();Coding004.MidNode(tree, result);Assert.Equal(JsonConvert.SerializeObject(midTree), JsonConvert.SerializeObject(result));} 想入非非扩展思维发挥想象 1. 熟悉二叉树2. 熟悉二叉树的几种遍历3. 熟悉队列先进先出4. 熟悉递归 其他系列的文章 面试题【从尾到头打印链表】 面试题【字符串替换空格】 面试题【二维数组中的查找】转载于:https://www.cnblogs.com/zhao123/p/11138608.html
