利用二叉树层序遍历输出每层数据

快来打我* 2022-06-09 08:17 127阅读 0赞

107. Binary Tree Level Order Traversal II

Given a binary tree, return the bottom-up level order traversal of its nodes' values. (ie, from left to right, level by level from leaf to root).

For example:  
Given binary tree `[3,9,20,null,null,15,7]`,

3
       / \
      9  20
        /  \
       15   7

return its bottom-up level order traversal as:

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

本题的思路也是层序遍历，同时通过控制队列大小来控制位于同一层，可以认为与[求二叉树每层平均值][Link 1]思路一致。

代码如下：

/**
     * Definition for a binary tree node.
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
     * };
     */
    class Solution {
    public:
        vector<vector<int>> levelOrderBottom(TreeNode* root) {
            vector<vector<int>> v1;
            vector<vector<int>> v;
            vector<int> v2;
            TreeNode *temp = root;
            queue<TreeNode *> q;
            if (temp == NULL)
                return v;
            q.push(temp);
            v2.push_back(temp->val);
            v1.push_back(v2);
            v2.clear();
            while (!q.empty())
            {
                int i = q.size();
                for (int j = 0; j < i; j++)
                {
                    TreeNode *top = q.front();
                    q.pop();
                    if (top->left != NULL)
                    {
                        q.push(top->left);
                        v2.push_back(top->left->val);
                    }
                    
                    if (top->right != NULL)
                     {
                        q.push(top->right);
                        v2.push_back(top->right->val);
                    }
                }
                if (!v2.empty())
                    v1.push_back(v2);
                v2.clear();
            }
            while (!v1.empty())
            {
                v.push_back(v1.back());
                v1.pop_back();
            }
            return v;
        }
    };

[Link 1]: http://blog.csdn.net/qwas12345qwas/article/details/77727214