2021-03-21 | 117.填充每个节点的下一个右侧节点指针 II

你的名字 2022-11-11 15:54 82阅读 0赞

### 1. 题目描述 ###

给定一个二叉树

struct Node { 
      int val;
      Node *left;
      Node *right;
      Node *next;
    }

填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 `NULL`。初始状态下，所有 next 指针都被设置为 `NULL`。

**进阶：**

*  你只能使用常量级额外空间。
 *  使用递归解题也符合要求，本题中递归程序占用的栈空间不算做额外的空间复杂度。

**示例：**  
![在这里插入图片描述][20210321161023442.png]

**输入**：root = \[1,2,3,4,5,null,7\]  
**输出：**\[1,\#,2,3,\#,4,5,7,\#\]  
**解释：** 给定二叉树如图 A 所示，你的函数应该填充它的每个 next 指针，以指向其下一个右侧节点，如图 B 所示。序列化输出按层序遍历顺序（由 next 指针连接），’\#’ 表示每层的末尾。

**提示：**

*  树中的节点数小于 `6000`
 *  `-100 <= node.val <= 100`

### 2. 解题思路 ###

对于这道题目，我们可以对树进行层序遍历，树的层序遍历是基于广度优先遍历的，按照层的顺序进行遍历，我们需要舒适话一个队列queue，这个队列中保存着当前层的节点。

当队列不为空的时候就记录当前队列的的长度len，当遍历这一层的时候，修改这一层节点的 next 指针，这样就可以把每一层都组织成链表。

**复杂度分析：**

*  时间复杂度：O(N)。其中N是树的节点数，我们需要遍历这棵树上所有的点，时间复杂度为 O(N)。
 *  空间复杂度：O(N)。其中N是树的节点数，我们需要初始化一个队列，它的长度最大不超过树的节点数。

### 3. 代码实现 ###

/** * // Definition for a Node. * function Node(val, left, right, next) { * this.val = val === undefined ? null : val; * this.left = left === undefined ? null : left; * this.right = right === undefined ? null : right; * this.next = next === undefined ? null : next; * }; */
    
    /** * @param {Node} root * @return {Node} */
    var connect = function(root) { 
        if (!root) { 
            return null;
        }
        const queue = [root];
        while (queue.length) { 
            const len = queue.length;
            let last = null;
            for (let i = 1; i <= len; ++i) { 
                let node = queue.shift();
                if (node.left) { 
                    queue.push(node.left);
                }
                if (node.right) { 
                    queue.push(node.right);
                }
                if (i !== 1) { 
                    last.next = node;
                }
                last = node;
            }
        }
        return root;
    };

### 4. 提交结果 ###

![在这里插入图片描述][2021032116111127.png]

[20210321161023442.png]: /images/20221022/e4e13e5c3a02427c803e6682ffe2bf10.png?
[2021032116111127.png]: /images/20221022/34a43243b3ab47a0b2c97de90fd4c4d7.png?