根据前序和中序遍历构造二叉树

╰半夏微凉° 2022-08-12 00:10 156阅读 0赞

思想：递归实现

#include<iostream>
    #include<string>
    #include<stack>
    using namespace std;
    struct Node
    {
    	int value;
    	Node *left;
    	Node *right;
    };
    Node *ContructBinaryTree(int *pre,int *in,int length,Node *root)
    {
    	if(length == 0)
    		return NULL;
    	root = new Node();
    	root->value = pre[0];
    	root->left = NULL;//将左子树和右子树的节点地址初始化，防止出现野指针
    	root->right = NULL;
    	if(length == 1)
    		return root;
    	else
    	{
    		int mid;
    		for(int i = 0;i < length;++i)
    			if(in[i] == root->value)
    			{
    				mid = i;
    				break;
    			}
    		root->left = ContructBinaryTree(pre + 1,in,mid,root);//构造以root为根的左子树
    		root->right = ContructBinaryTree(pre + mid + 1,in + mid + 1,length - mid - 1,root);//构造以root为根的右子树
    		return root;
    	}
    }
    void preOrder(Node *head)
    {
    	if(head != NULL)
    	{
    		cout<<head->value<<endl;
    		preOrder(head->left);
    		preOrder(head->right);
    	}
    }
    int main()
    {
    	int pre[7] = {3,2,6,5,1,4,7};
    	int in[7] = {5,6,2,3,4,1,7};
    	Node *head = ContructBinaryTree(pre,in,7,head);
    	preOrder(head);
    	return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，156人围观）

还没有评论，来说两句吧...

相关阅读

相关 java根据前序与中序遍历序列构造二叉树

根据前序与中序遍历序列构造二叉树问题描述给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder

叁歲伎倆/ 2024年03月16日 11:18/ 0 赞/ 12 阅读

相关 889. 根据前序和后序遍历构造二叉树

题目来源 [889. 根据前序和后序遍历构造二叉树][889.] 题目描述 ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGV

分手后的思念是犯贱/ 2022年12月23日 03:52/ 0 赞/ 89 阅读

相关【LeetCode 889】根据前序和后序遍历构造二叉树

相似题目： [【LeetCode 105】从前序与中序遍历序列构造二叉树][LeetCode 105] [【LeetCode 106】从中序与后序遍历序列构造二叉

怼烎@/ 2022年11月30日 04:02/ 0 赞/ 124 阅读

相关根据前序遍历和中序遍历构建二叉树以及根据中序遍历后序遍历构建二叉树

<pre name="code" class="cpp">// / 算法说明：由中序遍历序列可知，第一个节点是根节点，由前序遍

妖狐艹你老母/ 2022年08月22日 01:30/ 0 赞/ 167 阅读

相关根据前序和中序遍历构造二叉树

思想：递归实现 include<iostream> include<string> include<stack> using namespac

╰半夏微凉°/ 2022年08月12日 00:10/ 0 赞/ 157 阅读

相关根据前序遍历和中序遍历重建二叉树

/ Definition for binary tree / public class TreeNode {

落日映苍穹つ/ 2022年06月17日 08:38/ 0 赞/ 161 阅读

相关根据中序和前序遍历构建二叉树

面试题6：输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历都不含重复的数字 BinaryTreeNode constructCo

秒速五厘米/ 2022年06月17日 06:46/ 0 赞/ 181 阅读

相关根据前序和中序遍历重建二叉树 java

根据前序和中序遍历重建二叉树 java 题目描述输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如

超、凢脫俗/ 2022年05月09日 09:30/ 0 赞/ 179 阅读

相关根据前序(后序)和中序遍历创建二叉树

1. 根据前序和中序遍历创建二叉树 2. 根据后序和中序遍历创建二叉树注：如果仅仅知道三种遍历中的任何一种是无法准确还原一颗二叉树的前序和中序创建二叉树例如

爱被打了一巴掌/ 2022年05月08日 15:48/ 0 赞/ 226 阅读

相关根据前序遍历和中序遍历构建二叉树

根据树前序遍历和中序遍历构建二叉树问题：已知一个二叉树前序遍历为：ABDEGCFH，中序遍历为：DBGEACHF，则该二叉树的后序遍历为？ > 思路是这样的：1：根据

Love The Way You Lie/ 2021年09月29日 05:50/ 0 赞/ 372 阅读