题目

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,#,#,15,7},



return its bottom-up level order traversal as:

分析

与LeetCode（103） Binary Tree Zigzag Level Order Traversal 以及 LeetCode（102） Binary Tree Level Order Traversal 本质相同的题目，只不过灵活调整结果返回格式罢了。

AC代码

/**

 * 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) {

        //层次遍历，分层存储

        if (!root)

            return vector<vector<int> >();

        vector<vector<int> > ret;

        //定义两个队列，一个存储所有的父节点,另一个存储他们的子节点也就是子层

        queue<TreeNode *> parents;

        parents.push(root);

        while (!parents.empty())

        {

            //存储当前层的遍历结果

            vector<int> tmp;

            //定义队列存储他们的子节点也就是子层

            queue<TreeNode *> childs;

            while (!parents.empty())

            {

                TreeNode *node = parents.front();

                tmp.push_back(node->val);

                //弹出当前父节点

                parents.pop();

                if (node->left)

                    childs.push(node->left);

                if (node->right)

                    childs.push(node->right);

            }

            //存储当前层的遍历结果

            ret.push_back(tmp);

            //遍历下一层

            parents = childs;

        }

        //反转遍历结果 由下向上存储

        reverse(ret.begin(), ret.end());

        return ret;

    }

};

GitHub测试程序源码