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

3   / \  9  20    /  \   15   7

return its bottom-up level order traversal as:

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

从底部层序遍历其实还是从顶部开始遍历，只不过最后存储的方式有所改变，可以参见我之前的博文。代码如下：

解法一：

class Solution {public:    vector
     
      
        > levelOrderBottom(TreeNode *root) {        vector
       
        
          > res;        if (root == NULL) return res;        queue
         
           q;        q.push(root);        while (!q.empty()) {            vector
          
            oneLevel; int size = q.size(); for (int i = 0; i < size; ++i) { TreeNode *node = q.front(); q.pop(); oneLevel.push_back(node->val); if (node->left) q.push(node->left); if (node->right) q.push(node->right); } res.insert(res.begin(), oneLevel); } return res; }};

下面我们来看递归的解法，核心就在于我们需要一个二维数组，和一个变量level，当level递归到上一层的个数，我们新建一个空层，继续往里面加数字，参见代码如下：

解法二：

class Solution {public:    vector
     
      
       > levelOrderBottom(TreeNode* root) {        vector
       
        
          > res;        levelorder(root, 0, res);        return vector
         
          
            > (res.rbegin(), res.rend()); } void levelorder(TreeNode *root, int level, vector
           
            
              > &res) { if (!root) return; if (res.size() == level) res.push_back({}); res[level].push_back(root->val); if (root->left) levelorder(root->left, level + 1, res); if (root->right) levelorder(root->right, level + 1, res); }};

本文转自博客园的博客，原文链接：

，如需转载请自行联系原博主。