剑指Offer刷题（二十一）：栈的压入、弹出序列

题目

输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4，5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。（注意：这两个序列的长度是相等的）

思路

借助一个栈,如果栈空则从压入序列中加入一个元素,当栈中有元素时则比较它栈顶元素与出栈顺序的元素是否匹配,如果不匹配就压入一个元素,直到有匹配的,如果元素压入完了还没有匹配的则说明，这个出栈序列有问题.

C++


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

class  Solution{
public:
    bool is_right_out_squence(vector<int> instack,vector<int> outstack){
        int in_number=instack.size();
        int out_number=outstack.size();
        if(in_number!=out_number){
            return false;
        }
        stack<int> S1;
        int top=0;
        for(int i=0;i<out_number;i++){
          if(S1.empty()){
            S1.push(instack[top]);
            top++;
          }

          while(S1.top()!=outstack[i]){
            if(top==in_number){

                return false;
            }
            S1.push(instack[top]);
            top++;

          }
          S1.pop();


        }
        return true;



    }

};
int main(){
    int a[]={1,2,3,4,5};
    int b[]={4,5,3,2,1};
    vector<int> input;
    vector<int> output;
    for(int i=0;i<5;i++){
        input.push_back(a[i]);
        output.push_back(b[i]);
    }
    Solution s;
    cout<<s.is_right_out_squence(input,output);
    return 0;
}

剑指Offer（二十二）刷题：从上往下打印二叉树

题目

从上往下打印出二叉树的每个节点，同层节点从左至右打印。

思想

用一个队列辅助实现.先打印本节点,然后将该节点的左右子节点压入队列中。(NULL不入队列).然后从该队列中弹出一个节点,递归的调用该函数.

C++

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

struct TreeNode{

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

};


class Solution{
public:
    void print_tree(TreeNode * root){
        if(root==NULL){
            return 0;
        }
        if(root->left!=NULL){
            Q.push(root->left);
        }
        if(root->right!=NULL){
            Q.push(root->right);
        }
        cout<<root->val<<endl;
        TreeNode* out=Q.pop();
        print_tree(out);
        if(Q.empty())
            return 0;


    }


private:
    queue<TreeNode*> Q;



};

剑指Offer刷题（二十三）：二叉搜索树的后序遍历序列

题目

输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes，否则输出No。假设输入的数组的任意两个数字都互不相同。

思路

二叉搜索树是一个很规矩的结构.
首先要了解这个二叉搜索树有哪些性质:

任意节点x,其左子树中的key不大于x.key,其右子树的key都不小于x.key
不同的二叉搜索树可以代表同一组值得集合
二叉搜索树的基本操作和树的高度成正比,所以如果一棵完全二叉树的话,最坏的运行时间为O(lgn),但是若是一个n个节点连接成的线性树,那么最坏的运行时间是O(n).
根节点是唯一一个parent指针指向NIL节点的节点
每一个节点至少包括key、left、right与parent 这四个属性,构建二叉搜索树,必须存在针对key的比较算法

本题的思路:如果后序遍历的形式为{5,7,6,9,11,10,8}，则可根据后序遍历的定义知道,8是一个根节点,并且5,6,7都是8的左子树里的节点,而9,11,10都是8的右子树里的节点.

C++

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

class Solution{
public:
    bool Is_sequence(vector<int>A){
        int N=A.size();
        if(N==1){
            return true;
        }
        vector<int> left;
        vector<int> right;

        for(int i=0;i<N-1;i++){
            if(A[i]<=A[N-1]){
                left.push_back(A[i]);
            }
            else{

                break;

            }
        }
        int leftnum=left.size();
        for(int i=leftnum;i<N-1;i++){
            if(A[i]>=A[N-1]){
                right.push_back(A[i]);
            }
            else{
                return false;
            }
        }
        int rightnum=right.size();
        if(leftnum==0&&rightnum!=0){
            return Is_sequence(right);
        }
        else if(leftnum!=0&&rightnum==0){
            return Is_sequence(left);
        }
        else{
            return Is_sequence(left)&&Is_sequence(right);
        }
    }



};

int main()
{
    vector<int> S1;
    int a[]={5,7,6,9,11,10,8};
    for(int i=0;i<7;i++){
        S1.push_back(a[i]);
    }
    Solution s;
    cout<<s.Is_sequence(S1);

    return 0;
}