116. 填充每个节点的下一个右侧节点指针（JS实现）

傷城~ 2023-02-21 09:15 11阅读 0赞

## 1 题目 ##

> 给定一个完美二叉树，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：  
> struct Node \{  
> int val;  
> Node \*left;  
> Node \*right;  
> Node \*next;  
> \}  
> 填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。  
> 初始状态下，所有 next 指针都被设置为 NULL。  
> 示例：  
> 输入：\{“KaTeX parse error: Expected '\}', got 'EOF' at end of input: …":"1","left":\{"id”:“2”,“left”:\{“KaTeX parse error: Expected 'EOF', got '\}' at position 53: …t":null,"val":4\}̲,"next":null,"r…id”:“4”,“left”:null,“next”:null,“right”:null,“val”:5\},“val”:2\},“next”:null,“right”:\{“KaTeX parse error: Expected '\}', got 'EOF' at end of input: …":"5","left":\{"id”:“6”,“left”:null,“next”:null,“right”:null,“val”:6\},“next”:null,“right”:\{“KaTeX parse error: Expected 'EOF', got '\}' at position 53: …t":null,"val":7\}̲,"val":3\},"val"…id”:“1”,“left”:\{“KaTeX parse error: Expected '\}', got 'EOF' at end of input: …":"2","left":\{"id”:“3”,“left”:null,“next”:\{“KaTeX parse error: Expected '\}', got 'EOF' at end of input: …:null,"next":\{"id”:“5”,“left”:null,“next”:\{“KaTeX parse error: Expected 'EOF', got '\}' at position 53: …t":null,"val":7\}̲,"right":null,"…id”:“7”,“left”:\{“KaTeX parse error: Expected 'EOF', got '\}' at position 9: ref":"5"\}̲,"next":null,"r…ref”:“6”\},“val”:3\},“right”:\{“KaTeX parse error: Expected 'EOF', got '\}' at position 9: ref":"4"\}̲,"val":2\},"next…ref”:“7”\},“val”:1\}  
> 解释：给定二叉树如图 A 所示，你的函数应该填充它的每个 next 指针，以指向其下一个右侧节点，如图 B 所示。  
> 提示：  
> 你只能使用常量级额外空间。  
> 使用递归解题也符合要求，本题中递归程序占用的栈空间不算做额外的空间复杂度。

## 2 思路 ##

**这道题的主要思路是使用层序遍历的方法，逐层遍历节点，并连接相邻的节点， 题解比较巧妙，为了只使用O(1)的额外空间，其在层序遍历时，即连接当前节点的左右子节点，通过next指针链接兄弟节点的子节点**

## 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) { 
      let queue = [root];
      let temp = [];
      let p, pre = root;
    
      while (queue.length > 0 || temp.length > 0) { 
        if (queue.length === 0) { 
          queue = temp;
          temp = [];
          pre.next = null;
          pre = null;
        }
        p = queue.shift();
        if (!p) continue;
        temp.push(p.left);
        temp.push(p.right);
    
        if (!pre) { 
          pre = p;
        } else { 
          pre.next = p;
          pre = p;
        }
      }
    
      return root;
    };