Leetcode107:二叉树的层次遍历2

深碍√TFBOYSˉ_ 2023-10-07 13:59 38阅读 0赞

## Leetcode107:二叉树的层次遍历2 ##

#### 题目： ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NzA5OTkw_size_16_color_FFFFFF_t_70]

#### 思路： ####

按层次遍历树后将二维vector按逆序输出

###### 迭代： ######

需使用queue模板类建立队列q，元素类型为指向树节点的指针。每次循环用一个一维vector存储一层树节点的值，通过出队列遍历并存储一层树节点，同时将它们的左右孩子入队。当q空时，遍历完毕退出。

先将树的根节点指针root入队，在进行遍历一层树节点前先创建一个一维vector用于存储一层树节点的值。计算当前q中的元素数，即为该层节点数，将其作为遍历循环的结束条件。在循环中将队头出队，将其指示节点的值  
push到vector中，同时将左右孩子入队。循环上述过程。

退出循环后，将vector push到二维vector中。

当队列为空时，遍历结束，用STL中的reverse函数将二维vector变为逆序，二维vector的逆序即为vector的第一个行向量与最后一个行向量互换，第二个行向量与倒数第二个行向量互换，以此类推。

###### 递归： ######

递归函数原型有三个参数：指向树中节点的指针p、层数level（从0开始算起）、用于保存结果的二维vector的引用ans

p为空为递归函数结束的条件，当ans.size()==level时，表明此时需新增行向量。接下来将p指示的节点的值push到ans\[level\]中，并分别对p的左右子树调用递归函数，它们的level参数为level+1。

在主函数中调用递归函数，p为树的根节点，level的值为0。得到二维vector后将其逆序即为所求。

#### 代码： ####

###### 迭代： ######

/**
     * 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) {
        
            vector<vector<int>> ans;
            if( root==NULL )
                return ans;
            queue<TreeNode*> q;
            q.push( root );
            TreeNode* r;
            int n;
            int i;
            while( q.size()!=0 )
            {
           
                vector<int> temp;
                n=q.size();
                for( i=0;i<n;i++ )
                {
        
                    r=q.front();
                    q.pop();
                    temp.push_back( r->val );
                    if( r->left!=NULL )
                        q.push( r->left );
                    if( r->right!=NULL )
                        q.push( r->right );
                }
                ans.push_back( temp );
            }
            reverse( ans.begin(),ans.end() );
            return ans;
        }
    };

###### 递归： ######

/**
     * 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) {
        
            vector<vector<int>> ans;
            leveltraverse( ans,0,root );
            reverse( ans.begin(),ans.end() );
            return ans;
        }
        void leveltraverse( vector<vector<int>> &ans,int level,TreeNode* p )
        {
           
            if( p==NULL )
                return;
            if( ans.size()==level )
                ans.push_back( vector<int>() );
            ans[level].push_back( p->val );
            if( p->left!=NULL )
                leveltraverse( ans,level+1,p->left );
            if( p->right!=NULL )
                leveltraverse( ans,level+1,p->right );
        }
    };

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NzA5OTkw_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200429165118670.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NzA5OTkw,size_16,color_FFFFFF,t_70