剑指offer 面试题6:重建二叉树

简介:

题目

  输入某二叉树的前序遍历和中序遍历,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含有重复的数字。

  例如,前序遍历序列:{1,2,3,7,3,5,6,8},中序遍历序列:{4,7,2,1,5,3,8,6}

答案

  前序遍历:

    前序遍历首先访问根结点然后遍历左子树,最后遍历右子树。在遍历左、右子树时,仍然先访问根结点,然后遍历左子树,最后遍历右子树。

  中序遍历:

    中序遍历首先遍历左子树,然后访问根结点,最后遍历右子树。在遍历左、右子树时,仍然先遍历左子树,再访问根结点,最后遍历右子树。

复制代码
#include <iostream>

using namespace std;

struct binary_tree_node{
    int value;
    binary_tree_node*  left;
    binary_tree_node*  right;
};

binary_tree_node* binary_tree_constuct(int* preorder, int* inorder, int length);

int main()
{
    int pre[8] = {1,2,4,7,3,5,6,8};
    int in[8]  = {4,7,2,1,5,3,8,6};

    binary_tree_node* root = binary_tree_constuct(pre, in, 8);
}

binary_tree_node* construct_method(int* preorder, int* endpreorder, int* inorder, int* endinorder)
{
    int root_value = preorder[0];
    binary_tree_node* root = new binary_tree_node();
    root->left = NULL;
    root->right = NULL;

    cout<<root_value<<" ";

    if(preorder == endpreorder && inorder == endinorder)
        return root;

    int* rootIndex = preorder;
    rootIndex++;
    while(*rootIndex != root_value && rootIndex < endpreorder)
        rootIndex++;

    int left_len = rootIndex - preorder;
    int* left_preorder_end = preorder + left_len;
    //left
    if(left_len > 0)
    {
        root->left = construct_method(preorder+1, left_preorder_end, inorder, rootIndex-1);
    }
    //right
    if(left_len < endpreorder - preorder)
    {
        root->right = construct_method(left_preorder_end+1, endpreorder, rootIndex+1, endinorder);
    }

    return root;
}

binary_tree_node* binary_tree_constuct(int* preorder, int* inorder, int length)
{
    if(preorder == NULL || inorder == NULL || length <= 0)
    {
        return NULL;
    }

    return construct_method(preorder, preorder+length-1, inorder,inorder+length-1);

}
复制代码

 本文转自cococo点点博客园博客,原文链接:http://www.cnblogs.com/coder2012/p/3280474.html,如需转载请自行联系原作者

相关文章
|
2月前
【一刷《剑指Offer》】面试题 23:从上往下打印二叉树
【一刷《剑指Offer》】面试题 23:从上往下打印二叉树
|
2月前
【一刷《剑指Offer》】面试题 22:栈的压入、弹出系列
【一刷《剑指Offer》】面试题 22:栈的压入、弹出系列
|
2月前
|
算法
【一刷《剑指Offer》】面试题 21:包含 main 函数的栈
【一刷《剑指Offer》】面试题 21:包含 main 函数的栈
|
2月前
【一刷《剑指Offer》】面试题 20:顺时针打印矩阵
【一刷《剑指Offer》】面试题 20:顺时针打印矩阵
|
2月前
【一刷《剑指Offer》】面试题 19:二叉树的镜像
【一刷《剑指Offer》】面试题 19:二叉树的镜像
|
2月前
【一刷《剑指Offer》】面试题 18:树的子结构
【一刷《剑指Offer》】面试题 18:树的子结构
|
2月前
【一刷《剑指Offer》】面试题 17:合并两个排序的链表
【一刷《剑指Offer》】面试题 17:合并两个排序的链表
|
2月前
【一刷《剑指Offer》】面试题 16:反转链表
【一刷《剑指Offer》】面试题 16:反转链表
|
2月前
【一刷《剑指Offer》】面试题 15:链表中倒数第 k 个结点
【一刷《剑指Offer》】面试题 15:链表中倒数第 k 个结点
|
2月前
|
C++
【一刷《剑指Offer》】面试题 14:调整数组顺序使奇数位于偶数前面
【一刷《剑指Offer》】面试题 14:调整数组顺序使奇数位于偶数前面