4/7-剑指offer

1.从上到下打印二叉树
思路：利用队列，每次打印一个节点的时候，如果该节点有子节点，就把该节点的子节点放到一个队列的末尾。然后到队列的头部取出最早进入队列的节点，重复前面的打印操作，知道队列中所有的节点都被打印出来。

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};*/
class Solution {
public:
    vector<int> PrintFromTopToBottom(TreeNode* root) {
        vector<int> res;
        queue<TreeNode*> node;
        if(root==nullptr) return res;
        node.push(root);
        while(node.size()!=0)
        {
            res.push_back(node.front()->val);
            TreeNode* p=node.front();
            node.pop();
            //按层遍历二叉树
            if(p->left)
                node.push(p->left);
            if(p->right)
                node.push(p->right);   
        }
        return res;
    }
};

问2：如果要按层换行打印呢？
思路：利用两个变量，一个变量a记录当前层中还未打印的节点数，另一个b记录下一层节点的数目。当打印一个数时，判断有无叶子节点，有b加一，将此节点从队列弹出，a--，如果a等于0，表示此层被打完，令a=b，b=0。

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};*/
class Solution {
public:
    void Print(TreeNode *root)
    {
        if(root==nullptr) return;
        queue<TreeNode*> q;
        q.push(root);
        int cur=1;
        int next=0;//两个重要变量
        while(q.size()!=0)
        {
            printf("%d",q.front()->val);
            TreeNode *p=q.front();
            q.pop();
            if(p->left)
            {
                q.push(p->left);
                next++;//下一层数目加一
            }
            if(p->right)
            {
                q.push(p->right);
                next++;//下一层数目加一                
            }
            cur--;
            if(cur==0)
            {
                printf("\n");
                cur=next;
                next=0;//打印完一行换下一行
            }
        }
    }
};

问3：如果要求之字形打印呢？
思路：利用两个栈，当打印某一层的节点时，把下一层的节点保存到相应的栈里。如果打印的是奇数层，则先左再右把子节点保存在第一个栈里，如果打印的是偶数层，则先右再左把子节点保存在第二个栈里。

/*
/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};
*/
class Solution {
public:
    vector<vector<int> > Print(TreeNode* pRoot) {
        vector<vector<int> > res;
        vector<int> v;
        if(pRoot==nullptr) return res;
        stack<TreeNode*> s[2];
        int cur=0;
        int next=1;
        s[cur].push(pRoot);
        while(!s[0].empty()||!s[1].empty())
        {
            TreeNode* p=s[cur].top();
            v.push_back(s[cur].top()->val);
            s[cur].pop();
            if(cur==0)
            {
                if(p->left)
                    s[next].push(p->left);
                if(p->right)
                    s[next].push(p->right);
            }
            else
            {
                if(p->right)
                    s[next].push(p->right);
                if(p->left)
                    s[next].push(p->left);
            }
            if(s[cur].empty())
            {
                res.push_back(v);
                v.clear();
                cur=1-cur;
                next=1-next;
            }
        }
        return res;
    }   
};

2.二叉搜索树的后序遍历序列
思路：二叉搜索树后序遍历的特点，最后一个点是根节点，前面第一部分是左子树节点的值，都小于根节点；第二部分是右子树节点的值，都比根节点的值大。我们可以采取递归的思路，首先找到左子树，然后找右子树，然后分别递归遍历左右子树是否符合条件。

class Solution {
public:
    bool VerifySquenceOfBST(vector<int> sequence) {
      /*BST的后序序列的合法序列是，对于一个序列S，最后一个元素是x （也就是根），如果去掉最后一个
      元素的序列为T，那么T满足：T可以分成两段，前一段（左子树）小于x，后一段（右子树）大于x，且
      这两段（子树）都是合法的后序序列*/
        //利用递归
        int i=0;
        int len=sequence.size();
        vector<int> left,right;
        if(len<=0) return false;
        int root=sequence[len-1];//根节点是数组最后一个元素
        for(;i<len-1;i++)
        {
            if(sequence[i]>root) break;//从头开始遍历，若大于根节点，左子树结束
            left.push_back(sequence[i]);
        }
        int j=i;
        for(;j<len-1;j++)
        {
            if(sequence[j]<root) return false;//遍历右子树，若小于根节点，返回false
            right.push_back(sequence[j]);
        }
        bool flag1=true;
        if(i>0)//有左子树再递归遍历左子树
        flag1=VerifySquenceOfBST(left);
        bool flag2=true;
        if(i<len-1)//有右子树再递归遍历右子树
        flag2=VerifySquenceOfBST(right);
        if(flag1&&flag2)
            return true;
        else
            return false;
    }
};

3.二叉树中和为某一值的路径
思路：利用前序遍历，访问一个节点，就将该节点添加在路径上，并且累加该节点的值。如果该节点为叶子节点，并且路径中节点值的和刚好符合条件，就打印一条路径。当节点访问结束后（到叶子节点），递归函数将自动回到它的父节点。但在推出函数前要在路径上删除当前节点并减去当前节点的值，以确保返回父节点时的路径刚好是从根节点到父节点。这里为了打印时得到路径所有的点，用vector代替了STL中的stack。

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};*/
class Solution {   
public:
    vector<vector<int>> result;
    vector<int> buf;
    vector<vector<int> > FindPath(TreeNode* root,int expectNumber) {
        //利用递归
        if(root==NULL) return result;
        buf.push_back(root->val);
        if((expectNumber-root->val)==0&&root->left==NULL&&root->right==NULL)
        {
            result.push_back(buf);
        }
        FindPath(root->left,expectNumber-root->val);
        FindPath(root->right,expectNumber-root->val);
        if(buf.size()!=0)
            buf.pop_back();
        return result;
    }
};