剑指 Offer 07. 重建二叉树 C语言版

剑指 Offer 07. 重建二叉树 C语言版

文章目录

题目一、思路二、代码

三、 代码分析前序遍历的顺序是，根节点，左子树，右子树中序遍历的顺序是，左子树，根节点，右子树

---

题目

输入某二叉树的前序遍历和中序遍历的结果，请构建该二叉树并返回其根节点。

假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

示例 1:

Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
Output: [3,9,20,null,null,15,7]
示例 2:

Input: preorder = [-1], inorder = [-1]
Output: [-1]

一、思路

关于树的问题，最多的解法就是分治法与递归法，这里采取分治法，我们对每个子树都去调用建立二叉树函数，实现产生整个树。

二、代码

代码如下：

struct TreeNode* buildTree(int* preorder, int preorderSize, int* inorder, int inorderSize){
    if(preorderSize==0)
        return NULL;
    struct TreeNode *root=(struct TreeNode*)malloc(sizeof(struct TreeNode));
    root->val=preorder[0];//前序遍历的第一个节点是根节点
    int i;
    for(i=0;ileft=buildTree(&preorder[1],i,&inorder[0],i);
    root->right=buildTree(&preorder[i+1],preorderSize-i-1,&inorder[i+1],preorderSize-i-1);
    return root;
}

三、 代码分析

首先要说明的是，前序遍历与中序遍历的特点

前序遍历的顺序是，根节点，左子树，右子树 中序遍历的顺序是，左子树，根节点，右子树

1.首先我们通过前序遍历得知根节点的值。
2.然后在中序遍历中，找到根节点的位置。
3.在中序遍历中，根节点之前即为左子树的中序遍历，之后为右子树的中序遍历。
4.通过子树长度，在前序遍历中划分出左子树的前序遍历，之后为右子树的前序遍历。

举例说明：

    for(i=0;i 
此时i = 1,即为左子树长度，右子树长度为 preorderSize - i - 1;
 左子树的前序遍历为preorder[1]开始,长度为i
 左子树的中序遍历为inorder[0]开始,长度为i
 右子树的前序遍历为preorder[i+1]开始,长度为preorderSize - i - 1
 右子树的中序遍历为inorder[i+1]开始,长度为preorderSize - i - 1
					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/5703370.html