剑指offer刷题(四)——重建二叉树

题目

输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。

思路

通常树有如下几种遍历方式:

前序遍历:先访问根节点,再访问左子结点,最后访问右子结点.
中序遍历:先访问左子结点,再访问根结点,最后访问右子结点
后序遍历:先访问左子结点,再访问右子结点,最后访问根结点.

本题为前序遍历和中序遍历,最少需要两种遍历方式,才能重建二叉树.

从前序遍历序列可以看出,该序列的第一个元素是这棵树的根结点,则可在中序遍历中确定这棵树的左子树和右子树.

C++

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
struct TreeNode
{
int val;
TreeNode *left;
TreeNode *right;

TreeNode(int x):val(x),left(NULL),right(NULL){}

};

class Solution{
public:
    TreeNode *reConstructBinaryTree(vector<int> pre,vector<int> vin){
    if(pre.size()==0)
    {
        return NULL;
    }
    vector<int> left_pre,right_pre,left_vin,right_vin;
    TreeNode* head=new TreeNode(pre[0]);

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

    }
    for(int i=0;i<root;i++){
        left_vin.push_back(vin[i]);
        left_pre.push_back(pre[i+1]);
    }
    for(int i=root+1;i<pre.size();i++){
        left_vin.push_back(vin[i]);
        left_pre.push_back(pre[i]);
    }
    head->left=reConstructBinaryTree(left_pre,left_vin);
    head->right=reConstructBinaryTree(right_pre,right_vin);
    return head;
    }


};

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

vector<int> pre;
vector<int> vin;
for(int i=0;i<8;i++)
{
    pre.push_back(a[i]);
    vin.push_back(b[i]);
}
Solution s;
s.reConstructBinaryTree(pre,vin);


return 0;
}

class Solution:
    # 返回构造的TreeNode根节



    def reConstructBinaryTree(self, pre, tin):
        # write code here
        if(len(tin)==0):
            return None



        root=TreeNode(pre[0])
        pos=tin.index(pre[0])
        lefttin=tin[:pos]
        if(pos+1!=len(tin)):
            righttin=tin[pos+1:]
        else:
            righttin=[]
        leftnum=len(lefttin)
        rightnum=len(righttin)
        leftpre=pre[1:1+leftnum]
        rightpre=pre[1+leftnum:]
        root.left=self.reConstructBinaryTree(leftpre,lefttin)
        root.right=self.reConstructBinaryTree(rightpre,righttin)
        return root

剑指offer刷题(四)——用两个栈来实现队列

题目

用两个栈来实现一个队列，完成队列的Push和Pop操作。队列中的元素为int类型。

思路

栈的特点的先进后出,而队列的特点是先进先出.如何用两个栈来实现队列的先进先出.我的想法是:当要push时,将元素放入一个栈中(如果两个栈都为空,则随机找一个栈放入元素,如果一个栈非空,则push元素进这个栈中,保持另一个栈为空)。当要pop时,由于一个栈有元素,一个栈维空,则先将一个栈的元素全部倒入另一个栈中,再从这个栈中pop()出一个元素,之后再将元素全倒入另一个栈中.所以可以看出一个栈专门用来push的,一个栈专门用来pop的。由此可以实现队列的先进先出.

C++

#include<stack>
#include<iostream>
using namespace std;
class Solution
{
public:

    void push(int x)
    {
        pushstack.push(x);


    }
    int pop()
    {
        if(!pushstack.empty())
        {

            while(!pushstack.empty())
            {
                int y=pushstack.top();
                pushstack.pop();
                popstack.push(y);
            }
            int out=popstack.top();
            popstack.pop();
            while(!popstack.empty())
            {
                int y=popstack.top();
                popstack.pop();
                pushstack.push(y);
            }

            return out;
        }
        else{
            cout<<"empty already"<<endl;
            return -1;
        }
    }
private:
    stack<int> pushstack;
    stack<int> popstack;
};

int main()
{
    int  a[]={1,3,4,3,4,5,6,7};
    Solution s;
    for(int i=0;i<8;i++)
    {
        s.push(a[i]);
    }
    for(int i=0;i<8;i++)
    {
        cout<<s.pop()<<endl;
    }

    return 0;
}

Python
自己初始化L1与L2

class Solution:
    def __init__(self):
        self.L1=[]
        self.L2=[]
    def push(self, node):
        # write code here
        self.L1.append(node)    
    def pop(self):
        # return xx
        while(len(self.L1)!=0):
            x=self.L1.pop()
            self.L2.append(x)
        out=self.L2.pop()
        while(len(self.L2)!=0):
            x=self.L2.pop()
            self.L1.append(x)
        return out