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]
]

---

不知道这一题存在的必要性在哪里，解题方法和上一题LeetCode Binary Tree Level Order Traversal一模一样，不管是递归还是迭代，都只要在最后把结果reverse一下就好了。
完整代码如下：

class Solution {
public:
    vector<vector<int> > levelOrderBottom(TreeNode* root)
    {
        vector<vector<int> > ans;
        if (root == NULL)
            return ans;
        queue<TreeNode*> tree;
        tree.push(root);
        TreeNode* f;
        while (!tree.empty()) {
            int n = tree.size();
            vector<int> one_level;
            for (int i = 0; i < n; i++) {
                f = tree.front();
                tree.pop();
                one_level.push_back(f->val);
                if (f->left != NULL)
                    tree.push(f->left);
                if (f->right != NULL)
                    tree.push(f->right);
            }
            ans.push_back(one_level);
        }
        reverse(ans.begin(), ans.end());
        return ans;
    }
};

本代码提交AC，用时6MS。

二刷。还可以借助栈：

class Solution {
public:
	vector<vector<int>> levelOrderBottom(TreeNode* root) {
		if (root == NULL)return {};

		stack<vector<int>> stk;
		queue<TreeNode*> q;
		q.push(root);
		while (!q.empty()) {
			int n = q.size();
			vector<int> cur_level;
			while (n--) {
				TreeNode* front_tn = q.front();
				q.pop();
				cur_level.push_back(front_tn->val);
				if (front_tn->left != NULL)q.push(front_tn->left);
				if (front_tn->right != NULL)q.push(front_tn->right);
			}
			stk.push(cur_level);
		}
		vector<vector<int>> ans;
		while (!stk.empty()) {
			ans.push_back(stk.top());
			stk.pop();
		}
		return ans;
	}
};

本代码提交AC，用时4MS。