Leetcode: Binary Tree Level Order Traversal II

旧城等待， 2022-08-07 04:39 18阅读 0赞

题目：

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}`,

3
       / \
      9  20
        /  \
       15   7

return its bottom-up level order traversal as:

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

分析：

这道题目跟上道题目很相似 [ Leetcode: Binary Tree Level Order Traversal ][Leetcode_ Binary Tree Level Order Traversal]，唯一不同的就是返回结果是从子叶节点到根节点，所以我们只需要将结果翻转下就好了！

参考代码：

/**
     * Definition for binary tree
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
     * };
     */
    class Solution
    {
    private:
        void visit(TreeNode *node, int depth, vector<vector<int>> &result)
        {
        	if (node == NULL)
        	{
        		return;
        	}
        
        	if (result.size() > depth)
        	{
        		result[depth].push_back(node->val);
        	}
        	else
        	{
        		vector<int> level;
        		level.push_back(node->val);
        		result.push_back(level);
        	}
        
        	visit(node->left, depth + 1, result);
        	visit(node->right, depth + 1, result);
        }
    public:
        vector<vector<int>> levelOrderBottom(TreeNode *root)
        {
        	vector<vector<int>> result;
        	visit(root, 0, result);
            //就只有最后一句不一样，返回值对vector做了一个reverse
        	return vector<vector<int>>(result.rbegin(), result.rend());
        }
    };

[Leetcode_ Binary Tree Level Order Traversal]: http://blog.csdn.net/theonegis/article/details/44157357