Leetcode 117 -- 树&&bfs

题目描述

填充每个节点的下一个节点
题目要求我们填充每个节点的 \(next\) 指针，让它指向它的(同一层)右侧的节点，如果没有，指向 $NULL，（初始时全部指向 \(NULL\)）。

思路

看到关于二叉树的问题，首先要想到关于二叉树的一些常见遍历方式，
对于二叉树的遍历有：

1. 前序遍历
2. 中序遍历
3. 后序遍历
4. 深度优先搜索（DFS）
5. 宽度优先搜索（BFS）
   除了上面介绍的5种以外，还有 \(Morris\)（莫里斯）的前中后 \(3\) 种遍历方式，总共也就这 \(8\) 种。所以只要遇到二叉树相关的算法题，首先想到的就是上面的几种遍历方式，然后再稍加修改，基本上也就这个套路。

这题让求的就是让把二叉树中每行都串联起来，对于这道题来说最适合的就是 \(BFS\)。也就是一行一行的遍历，如下图所示

代码

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* left;
    Node* right;
    Node* next;

    Node() : val(0), left(NULL), right(NULL), next(NULL) {}

    Node(int _val) : val(_val), left(NULL), right(NULL), next(NULL) {}

    Node(int _val, Node* _left, Node* _right, Node* _next)
        : val(_val), left(_left), right(_right), next(_next) {}
};
*/

class Solution {
public:
    Node* connect(Node* root) {
        if(root == NULL)    return NULL;
        
        queue<Node*> q;
        q.push(root);
        while(q.size())
        {
            Node *pre = NULL;
            int n = q.size();
            for(int i = 0; i < n; i ++ ) // 每次遍历一层
            {
                auto t = q.front(); q.pop(); 
                if(pre) pre->next = t, pre = t;
                else pre = t;
                if(t->left)     q.push(t->left);
                if(t->right)    q.push(t->right);
            }
        }
        return root;
    }
};