107. Binary Tree Level Order Traversal II.md

107. Binary Tree Level Order Traversal II

思路

题目的意思就是层序遍历的变形，从下往上、从左往右层序遍历。为此我们先正常层序遍历并用一个stack记录每一层的节点。然后再依次出栈即可。

下面简单说一下正常的层序遍历（即从上往下、从左往右）: 建立一个queue，然后先把根节点放进去，进入while循环，记录此刻的queue大小(设为size)， 并用一个for循环依次出队并遍历size个元素,此过程要将左右两个子节点入队。一次while循环即可得到一层的所有节点，以此类推，可以完成层序遍历。

时间复杂度和空间复杂度都是O(n)

C++

class Solution {
public:
    vector<vector<int>> levelOrderBottom(TreeNode* root) {
        vector<vector<int>>res;
        if(root == NULL) return res;
        queue<TreeNode *>q;
        stack<vector<int>>stk;
        TreeNode *p;
        
        q.push(root);
        while(!q.empty()){
            vector<int>level; // 记录此层的所有节点
            for(int i = q.size(); i > 0; i--){
                p = q.front();
                q.pop();
                level.push_back(p -> val);
                if(p -> left) q.push(p -> left);
                if(p -> right) q.push(p -> right); // 如果想从下往上、从右往左层序遍历的话只需把词句和上一句调换位置即可
            }
            stk.push(level);
        }
        // 上面的过程就是正常的层序遍历过程
        
        while(!stk.empty()){
            res.push_back(stk.top());
            stk.pop();
        }
        return res;
    }
};