LeetCode 0107. Sequence traversal of binary tree II - another method

【LetMeFly】107. Sequence traversal of binary tree II

Force button topic link ：https://leetcode.cn/problems/binary-tree-level-order-traversal-ii/

Give you the root node of the binary tree root , Returns its node value Bottom up sequence traversal . （ That is, from the layer where the leaf node is to the layer where the root node is , Traversal layer by layer from left to right ）

 

Example 1：

 Input ：root = [3,9,20,null,null,15,7]
 Output ：[[15,7],[9,20],[3]]

Example 2：

 Input ：root = [1]
 Output ：[[1]]

Example 3：

 Input ：root = []
 Output ：[]

 

Tips ：

• The number of nodes in the tree is in the range [0, 2000] Inside
• -1000 <= Node.val <= 1000

Method 1 ： Priority queue

And The previous method Different , This time I decided not to use pair<TreeNode*, int>, But directly TreeNode* The team .

If you don't understand, you can read the previous blog first ：https://letmefly.blog.csdn.net/article/details/125584554

that , period int Number of layers of type , How to determine which nodes belong to the same layer ？

It's also very simple , When the queue is not empty , Record the total number of elements in the queue , The number of these elements is the number of nodes in the current last layer .

then , We use a cycle , Add all these elements to the same layer of the answer （ At the same time, join the child nodes ） that will do .

• Time complexity $O(N)$, among $N$ Is the number of nodes .
• Spatial complexity $O(N2)$, among $N2$ Is the number of nodes in the layer with the most nodes .

AC Code

C++

class Solution {
    
public:
    vector<vector<int>> levelOrderBottom(TreeNode* root) {
    
        vector<vector<int>> ans;
        queue<TreeNode*> q;
        if (root)
            q.push(root);
        int layer = -1;
        while (q.size()) {
    
            ans.push_back({
    });
            layer++;
            int thisLayerNum = q.size();
            while (thisLayerNum--) {
    
                TreeNode* thisNode = q.front();
                q.pop();
                ans[layer].push_back(thisNode->val);
                if (thisNode->left)
                    q.push(thisNode->left);
                if (thisNode->right)
                    q.push(thisNode->right);
            }
        }
        reverse(ans.begin(), ans.end());  //  Be careful , Here is the question, which requires you to traverse from the last level , therefore reverse The following . Under normal circumstances, the level traversal does not need reverse Of 
        return ans;
    }
};

Synchronous posting on CSDN, Originality is not easy. , Reprint please attach Link to the original text Oh ~
Tisfy：https://letmefly.blog.csdn.net/article/details/125610699