力扣刷题之二叉树的层序遍历

二叉树的层序遍历

**广度优先搜索 **

我们可以用一种巧妙的方法修改广度优先搜索：

• 首先根元素入队

• 当队列不为空的时候

   1.求当前队列的长度 Si
    2.依次从队列中取 Si 个元素进行拓展，然后进入下一次迭代
  

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) { 
     //初始化队列同时将第一层节点加入队列中，即根节点
      queue<TreeNode*> az;
      vector<vector<int>> sz;
      if(root==nullptr)
      {
          return sz;
      }
      az.push(root);

      //外层的while循环迭代的是层数
      while(!az.empty())
      {
       //记录当前队列大小
          int size=az.size();
          vector<int> a;
           //遍历这一层的所有节点
          for(int i=0;i<size;i++)
          { 
              //从队首取出元素
              TreeNode* node=az.front();
              az.pop();
              a.push_back(node->val);
              if(node->left) az.push(node->left);
              if(node->right)az.push(node->right);
          }
          sz.push_back(a);
      }
      return sz;
    }
};

大家请记住这个模板,后面的几个练习题，都是在这个上面稍作更改.

二叉树的层序遍历II

相对于上面的题目，我们就需要把数组翻转一下就好了.

class Solution {
public:
    vector<vector<int>> levelOrderBottom(TreeNode* root) {
         vector<vector<int>> az;
         queue<TreeNode*> sz;
          if(root==nullptr)
          {
              return az;
          }
          sz.push(root);
           
         while(!sz.empty())
         {
             vector<int> a;
             int size=sz.size();
             for(int i=0;i<size;i++)
         {
             TreeNode* node=sz.front();
             sz.pop();
             a.push_back(node->val);
             if(node->left) sz.push(node->left);
             if(node->right) sz.push(node->right);
         }
         az.push_back(a);
         }
         reverse(az.begin(),az.end());
        return az;
    }
};

二叉树的右视图

层序遍历的时候，判断是否遍历到单层的最后面的元素，如果是，就放进result数组中，随后返回result就可以了。

class Solution {
public:
    vector<int> rightSideView(TreeNode* root) {
    vector<int> az;
    queue<TreeNode*> sz;
    if(root==nullptr)
    {
        return az;
    }
    sz.push(root);
    while(!sz.empty())
    {
        int size=sz.size();
        for(int i=0;i<size;i++)
        {
            TreeNode* node=sz.front();
            sz.pop();
            if(i==size-1)
            {
                az.push_back(node->val);
            }
            if(node->left)sz.push(node->left);
            if(node->right)sz.push(node->right);
        }
    }
    return az;
    }
};

二叉树的层平均值

本题就是层序遍历的时候把一层求个总和在取一个均值。

class Solution {
public:
    vector<double> averageOfLevels(TreeNode* root) {
     vector<double> az;
     queue<TreeNode*> sz;
     if(root==nullptr)
{
    return az;
}     sz.push(root);
     while(!sz.empty())
    {
         double sum=0;
        int size=sz.size();
        for(int i=0;i<size;i++)
        {
            TreeNode* node=sz.front();
            sz.pop();
            sum+=node->val;
            if(node->left)sz.push(node->left);
            if(node->right)sz.push(node->right);
        }
        az.push_back(sum/size);
    }
     return az;
    }
};

N叉树的层序遍历

这题就是跟第一题基本一样的，只不过节点多了几个孩子

class Solution {
public:
    vector<vector<int>> levelOrder(Node* root) {
        vector<vector<int>> az;
        queue<Node*> sz;
        if(root==nullptr){
            return az;
        }
        sz.push(root);
        while(!sz.empty())
        {
            vector<int> a;
           int size=sz.size();
           for(int i=0;i<size;i++)
           {
               Node* node=sz.front();
               sz.pop();
               a.push_back(node->val);
               for(int i=0;i<node->children.size();i++)
               {
                   if(node->children[i])
                   sz.push(node->children[i]);
               }
           }
           az.push_back(a);

        }
        return az;
    }
};

在每个树行中找最大值

class Solution {
public:
    vector<int> largestValues(TreeNode* root) {
    vector<int> az;
    queue<TreeNode*> sz;
    if(root==nullptr)
    {
        return az;
    }
    sz.push(root);
    while(!sz.empty())
    {
        int size=sz.size();
        int max=INT_MIN;
       for(int i=0;i<size;i++)
       {
          TreeNode* node=sz.front();
          sz.pop();
          max=max>node->val?max:node->val;
          if(node->left) sz.push(node->left);
          if(node->right)sz.push(node->right);
       }
       az.push_back(max);
    }
    return az;
    }
};

填充每个节点的下一个右侧节点指针

回想一下二叉树的层次遍历，用广度优先实现的时候，就是层层遍历，每层临时遍历的节点都会放到一个队列中。队列中保存了第 i 层节点的信息，我们利用这个特点，将队列中的元素都串联一遍就可以了。

class Solution {
    public Node connect(Node root) {
        if (root == null) {
            return root;
        }
        
        // 初始化队列同时将第一层节点加入队列中，即根节点
        Queue<Node> queue = new LinkedList<Node>(); 
        queue.add(root);
        
        // 外层的 while 循环迭代的是层数
        while (!queue.isEmpty()) {
            
            // 记录当前队列大小
            int size = queue.size();
            
            // 遍历这一层的所有节点
            for (int i = 0; i < size; i++) {
                
                // 从队首取出元素
                Node node = queue.poll();
                
                // 连接
                if (i < size - 1) {
                    node.next = queue.peek();
                }
                
                // 拓展下一层节点
                if (node.left != null) {
                    queue.add(node.left);
                }
                if (node.right != null) {
                    queue.add(node.right);
                }
            }
        }
        
        // 返回根节点
        return root;
    }
}

填充每个节点的下一个右侧节点指针II

和上题是完全一样的

class Solution {
public:
    Node* connect(Node* root) {
        if (root == nullptr) {
            return root;
        }
        
        // 初始化队列同时将第一层节点加入队列中，即根节点
        queue<Node*> Q;
        Q.push(root);
        
        // 外层的 while 循环迭代的是层数
        while (!Q.empty()) {
            
            // 记录当前队列大小
            int size = Q.size();
            
            // 遍历这一层的所有节点
            for(int i = 0; i < size; i++) {
                
                // 从队首取出元素
                Node* node = Q.front();
                Q.pop();
                
                // 连接
                if (i < size - 1) {
                    node->next = Q.front();
                }
                
                // 拓展下一层节点
                if (node->left != nullptr) {
                    Q.push(node->left);
                }
                if (node->right != nullptr) {
                    Q.push(node->right);
                }
            }
        }
        
        // 返回根节点
        return root;
    }
};

二叉树的最大深度

这题前面有讲过， 可以参考这篇博客:力扣刷题之二叉树的最大深度_skeet follower的博客-CSDN博客

二叉树的最小深度

需要注意的是，只有当左右孩子都为空的时候，才说明遍历的最低点了。如果其中一个孩子为空则不是最低点

class Solution {
public:
    int minDepth(TreeNode* root) {
      queue<TreeNode*> az;
      if(root==nullptr)
      {
          return 0;
      }
      int depth=0;
      az.push(root);
      while(!az.empty())
      {
          int size=az.size();
          depth++;
          for(int i=0;i<size;i++)
          {
              TreeNode* node=az.front();
              az.pop();
              if(node->left) az.push(node->left);
              if(node->right)az.push(node->right);
              if(node->right==nullptr&&node->left==nullptr)
              {
                  return depth;
              }
          }
      }
      return depth;
    }
};