Binary Tree Level Order Traversal II

目录

• 题目链接
• 注意点
• 解法
• 小结

题目链接

Binary Tree Level Order Traversal - LeetCode

注意点

• 不要访问空结点

解法

解法一：递归，在Binary Tree Level Order Traversal - LeetCode的基础上将结果逆序即可。

/**
 * 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:
    typedef vector<vector<int>> v;
    typedef TreeNode* node;
    void bfs(int level,node n,v& ret)
    {
        if(ret.size() == level) ret.push_back({});
        ret[level].push_back(n->val);
        if(n->left) bfs(level+1,n->left,ret);
        if(n->right) bfs(level+1,n->right,ret);
    }
    vector<vector<int>> levelOrderBottom(TreeNode* root) {
        v ret;
        if(!root) return ret;
        queue<node> q;
        q.push(root);
        bfs(0,root,ret);
        reverse(ret.begin(),ret.end());
        return ret;
    }
};

解法二：非递归，同样在Binary Tree Level Order Traversal - LeetCode的基础上将结果逆序即可。

/**
 * 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:
    typedef vector<vector<int>> v;
    typedef TreeNode* node;
    vector<vector<int>> levelOrderBottom(TreeNode* root) {
        v ret;
        if(!root) return ret;
        queue<node> q;
        q.push(root);
        while(!q.empty())
        {
            vector<int> aLevel;
            for(int i = q.size();i > 0;--i)
            {
                node n = q.front();
                q.pop();
                aLevel.push_back(n->val);
                if(n->left) q.push(n->left);
                if(n->right) q.push(n->right);
            }
            ret.push_back(aLevel);
        }
        reverse(ret.begin(),ret.end());
        return ret;
    }
};

小结