题目描述

• 输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。
• 假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
• 例如，输入前序遍历序列 {1, 2, 4, 7, 3, 5, 6, 8} 和中序遍历序列 {4, 7, 2, 1, 5, 3, 8, 6}，则重建如下图所示的二叉树并输出它的头节点。
• 二叉树节点的定义如下:

struct TreeNode {
      int val;
      TreeNode *left;
      TreeNode *right;
};

思路解读

• 剑指Offer 62

代码

class Solution {
public:
    TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {
        int flag = 0;
        if(pre.size() > 1){
            TreeNode *p = new TreeNode(pre[0]);
            //p->val = pre[0];
            
            // 在中序遍历序列中找到根节点
            for(int i=0; i<vin.size(); i++){
                if(pre[0] == vin[i]){
                    flag = i;
                    break;
                }
            }

            vector<int> a;
            vector<int> b;
            a.assign(pre.begin()+1, pre.begin()+flag+1);
            b.assign(vin.begin(), vin.begin()+flag);
            p->left  = reConstructBinaryTree(a, b);

            a.assign(pre.begin()+flag+1, pre.begin()+pre.size());
            b.assign(vin.begin()+flag+1, vin.begin()+vin.size());
            p->right = reConstructBinaryTree(a, b);

            return p;
        }
        else if(pre.size() == 1){
            TreeNode *p = new TreeNode(pre[0]);
            //p->val = pre[0];
            return p;
        }
        else{
            return NULL;
        }
    }
};

总结展望

• 剑指Offer 这本书的题目确实不错..

附本地实现代码

#include<iostream>
#include<vector>
using namespace std;

struct TreeNode {
      int val;
      TreeNode *left;
      TreeNode *right;
};

class Solution {
    public:
        TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) 
        {
            int flag = 0;

            if(pre.size() > 1)
            {
                TreeNode *p = new TreeNode;
                p->val = pre[0];

                for(int i=0; i<vin.size(); i++){
                    if(pre[0] == vin[i])
                    {
                        flag = i;
                        break;
                    }
                }

                vector<int> a;
                vector<int> b;
                a.assign(pre.begin()+1, pre.begin()+flag+1);
                b.assign(vin.begin(), vin.begin()+flag);
                p->left  = reConstructBinaryTree(a, b);

                a.assign(pre.begin()+flag+1, pre.begin()+pre.size());
                b.assign(vin.begin()+flag+1, vin.begin()+vin.size());
                p->right = reConstructBinaryTree(a, b);

                return p;
            }
            else if(pre.size() == 1)
            {
                TreeNode *p = new TreeNode;
                p->val = pre[0];

                return p;
            }
            else
            {
                return NULL;
            }
            
        }

        // 前序遍历
        void print_Tree_qianxu(TreeNode *head)
        {
            if(head != NULL)
            {
                cout<<head->val<<" ";
                print_Tree_qianxu(head->left);
                print_Tree_qianxu(head->right);
            }
        }

        // 中序遍历
        void print_Tree_zhongxu(TreeNode *head)
        {
            if(head != NULL)
            {
                print_Tree_zhongxu(head->left);
                cout<<head->val<<" ";
                print_Tree_zhongxu(head->right);
            }
        }

        // 后序遍历
        void print_Tree__houxu(TreeNode *head)
        {
            if(head != NULL)
            {
                print_Tree__houxu(head->left);
                print_Tree__houxu(head->right);
                cout<<head->val<<" ";
            }
        }
};

int main()
{
    int a[8] = {1, 2, 4, 7, 3, 5, 6, 8};
    int b[8] = {4, 7, 2, 1, 5, 3, 8, 6};
    vector<int> pre;
    vector<int> vin;
    TreeNode *head;
    Solution ss;

    for(int i=0; i<8; i++)
    {
        pre.push_back(a[i]);
        vin.push_back(b[i]);
    }

    head = ss.reConstructBinaryTree(pre, vin);

    cout<<"前序遍历: ";
    ss.print_Tree_qianxu(head);
    cout<<endl;

    cout<<"中序遍历: ";
    ss.print_Tree_zhongxu(head);
    cout<<endl;

    cout<<"后序遍历: ";
    ss.print_Tree__houxu(head);
    cout<<endl;
}