讨论/《广度优先搜索》 - 练习:二叉树的层次遍历 II/
《广度优先搜索》 - 练习:二叉树的层次遍历 II
共 4 个回复

c++ 正序 + swap(reverse)

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    void reverseOp(vector<vector<int>>& ret) {
        int i = 0, j = ret.size() - 1;
        vector<int> temp;
        while(i <= j) {
            temp = ret[i];
            ret[i] = ret[j];
            ret[j] = temp;
            i++;
            j--;
        }
    }
    vector<vector<int>> levelOrderBottom(TreeNode* root) {
        //层序遍历
        if(root == nullptr) return {};
        vector<vector<int>> ret;
        vector<int> temp;
        queue<TreeNode*> Q;
        Q.push(root);
        while(!Q.empty()) {
            int curSize = Q.size();
            temp.clear();
            for(int i = 0; i < curSize; i++) {
                TreeNode* node = Q.front();
                temp.push_back(node->val);
                if(node->left != nullptr) Q.push(node->left);
                if(node->right != nullptr) Q.push(node->right);
                Q.pop();
            }
            ret.push_back(temp);
        }
        reverseOp(ret);
        return ret;
    }
};

是的~

这是正序遍历,还少一个reverse

class Solution:
    def levelOrderBottom(self, root: TreeNode) -> List[List[int]]:
        if not root: return []
        q = collections.deque([root])
        res = []
        while q :
            l = []
            for i in range(len(q)) :
                t = q.popleft()
                l.append(t.val)
                if t.left : q.append(t.left)
                if t.right : q.append(t.right)
            res.append(l)
        return res