[数据结构与算法]C++107.二叉树的层序遍历II

题目

给定一个二叉树，返回其节点值自底向上的层序遍历。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）。

解答思路

该题目和102题基本一样，只不过102题是自顶向下的层序遍历，该题是自底向上的层序遍历。所以解决方法分为两步：
第一步：二叉树的层序遍历，即问题102；
第二步：数组反转，该题可以参考双指针反转数组的相关题目，当然也可以使用reverse函数。
二叉树的层序遍历是个基本问题，需要用deuque结合迭代法来实现，基本方式就是遍历某一层时，将该层结点的左右子节点（如果存在）放进队列中，弹出该层遍历完的节点，该层结点遍历完之后，队内剩余元素的数量即为下一层结点的数量。依次操作，直到遍历完二叉树的最后一层。

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> result;
        if(root == nullptr)
            return result;
        queue<TreeNode*> myQueue;
        myQueue.push(root);
        while(!myQueue.empty()){
            int level = myQueue.size();
            result.push_back(vector<int>());
            for(int i=0; i<level; i++){
                auto p = myQueue.front();
                result.back().push_back(p->val);
                myQueue.pop();
                if(p->left!=nullptr)
                    myQueue.push(p->left);
                if(p->right!=nullptr)
                    myQueue.push(p->right);
            }
        }
        return result;
    }
};

另外，力扣中题目429. N 叉树的层序遍历，操作与该题目基本相同，区别在于添加children节点的方式不是left和right，具体实现见下述代码块：

class Solution {
public:
    vector<vector<int>> levelOrder(Node* root) {
        vector<vector<int>> result;
        if(root==nullptr){
            return result;
        }
        queue<Node*> q;
        q.push(root);
        while(!q.empty()){
            int number = q.size();
            vector<int> temp;
            for(int i=0; i<number; i++){
                auto p = q.front();
                temp.push_back(p->val);
                q.pop();
                for(int j=0; j<p->children.size(); j++){
                    q.push(p->children[j]);
                }
            }
            result.push_back(temp);
        }
        return result;
    }
};

第二步数组反转，采取双指针的方式，这里不再赘述，实现代码如下所示：

int left = 0; int right = result.size()-1;
        while(left < right){
            vector<int> temp = result[right];
            result[right] = result[left];
            result[left] = temp;
            right --;
            left ++;
        }