题解 | #求二叉树的层序遍历#

1、题目描述
给定一个二叉树，返回该二叉树层序遍历的结果，（从左到右，一层一层地遍历）。
例如：给定的二叉树是{3,9,20,#,#,15,7},

    3
   / \
  9  20
    /  \
   15   7

该二叉树层序遍历的结果是

[[3],[9,20],[15,7]]

层次遍历，通过队列来实现，整体思路就是先把根节点入队，然后出队，队为空就入前面出队的元素的左、右子树，不为空就继续出队头元素。
需要注意的是，题目给的返回值是二维类型，所以要额外定义一个辅助容器(一维类型)qvec,这个容器记录每层从左到右的元素，当该容器有元素的时候，就把他的内容输给res。

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

class Solution {
public:
    /**
     * 
     * @param root TreeNode类 
     * @return int整型vector<vector<>>
     */
    vector<vector<int> > levelOrder(TreeNode* root) {
        // write code here
        queue<TreeNode*> Queue;//利用队列实现
        vector<vector<int>> res;
        if(!root)
        {
            return res;
        }
        Queue.push(root);
        while(Queue.size()>0)
        {
            vector<int> qvec;
            int size = Queue.size();
            while(size>0)
            {
                TreeNode* node = Queue.front();
                qvec.push_back(node->val);
                Queue.pop();
                size--;
                if(node->left)
                    Queue.push(node->left);
                if(node->right)
                    Queue.push(node->right);
            }
            if(qvec.size()>0)
            {
                res.push_back(qvec);
            }
        }
        return res;
    }
};

2、题目描述
给定一个二叉树，返回该二叉树由底层到顶层的层序遍历，（从左向右，从叶子节点到根节点，一层一层的遍历）。
例如：给定的二叉树是{3,9,20,#,#,15,7},

    3
   / \
  9  20
    /  \
   15   7

该二叉树由底层到顶层层序遍历的结果是

[[15,7],[9,20],[3]]

我的思路是采用一个队列和一个栈来实现。队列用来将树按照正常层序遍历的顺序存放，栈用来将输出顺序反转。

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

class Solution {
public:
    /**
     * 
     * @param root TreeNode类 
     * @return int整型vector<vector<>>
     */
    vector<vector<int> > levelOrderBottom(TreeNode* root) {
        // write code here
        vector<vector<int>> res;
        queue<TreeNode*> Queue; //注意队列中数据存放类型
        Queue.push(root);

        stack<vector<int>> Stack;//注意栈中的数据存放类型

        if(!root)
            return res;
        while(Queue.size()>0)
        {
            vector<int> qvec;
            int size = Queue.size();
            while(size>0)
            {
                TreeNode* node = Queue.front();
                qvec.push_back(node->val);
                Queue.pop();
                size--;
                if(node->left)
                    Queue.push(node->left);
                if(node->right)
                    Queue.push(node->right);
            }
            if(qvec.size()>0)
            {
                Stack.push(qvec);//将每层从左到右的节点存到的容器入栈
            }
        }
        while(Stack.size()>0)
        {
            vector<int> rvec = Stack.top();
            Stack.pop();
            res.push_back(rvec);
        }
        return res;
    }
};