題目描述

• 輸入某二叉樹的前序遍歷和中序遍歷的結(jié)果，請重建該二叉樹杜秸。
• 假設(shè)輸入的前序遍歷和中序遍歷的結(jié)果中都不含重復(fù)的數(shù)字放仗。
• 例如，輸入前序遍歷序列 {1, 2, 4, 7, 3, 5, 6, 8} 和中序遍歷序列 {4, 7, 2, 1, 5, 3, 8, 6}撬碟，則重建如下圖所示的二叉樹并輸出它的頭節(jié)點诞挨。
• 二叉樹節(jié)點的定義如下:

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];
            
            // 在中序遍歷序列中找到根節(jié)點
            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;
        }
    }
};

總結(jié)展望

• 劍指Offer 這本書的題目確實不錯..

附本地實現(xiàn)代碼

#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;
}