【LeetCode 116】填充每个节点的下一个右侧节点指针

r囧r小猫 2022-11-30 04:06 108阅读 0赞

#### 题目描述 ####

给定一个完美二叉树，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：

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

填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。

初始状态下，所有 next 指针都被设置为 NULL。

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

输入：{ "$id":"1","left":{ "$id":"2","left":{ "$id":"3","left":null,"next":null,"right":null,"val":4},"next":null,"right":{ "$id":"4","left":null,"next":null,"right":null,"val":5},"val":2},"next":null,"right":{ "$id":"5","left":{ "$id":"6","left":null,"next":null,"right":null,"val":6},"next":null,"right":{ "$id":"7","left":null,"next":null,"right":null,"val":7},"val":3},"val":1}
    
    输出：{ "$id":"1","left":{ "$id":"2","left":{ "$id":"3","left":null,"next":{ "$id":"4","left":null,"next":{ "$id":"5","left":null,"next":{ "$id":"6","left":null,"next":null,"right":null,"val":7},"right":null,"val":6},"right":null,"val":5},"right":null,"val":4},"next":{ "$id":"7","left":{ "$ref":"5"},"next":null,"right":{ "$ref":"6"},"val":3},"right":{ "$ref":"4"},"val":2},"next":null,"right":{ "$ref":"7"},"val":1}

解释：给定二叉树如图 A 所示，你的函数应该填充它的每个 next 指针，以指向其下一个右侧节点，如图 B 所示。

提示：

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

#### 解题思路 ####

这里我们使用递归的方式来解决这个问题。我们对二叉树进行先序遍历。我们要讨论两种情况：**同一父节点的左右节点相连** 和 **非同一父节点的左右节点相连**，下面来看以下：

*  第一步，对于同一父节点的左右节点相连，将左节点的值指向右节点
 *  第二部，对于非同一父节点的左右节点相连，以图中的5和6为例，我们通过5的父节点2，找到他的右节点3，再通过3找到其左节点，并将5和相连3相连。

对于上面的步骤，进行递归，直至遍历完所有的节点。

此方法的**时间复杂度为O(n)**，**空间复杂度为O(1)**。

#### 代码实现 ####

/** * // 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
    	// 同一父节点的左右节点相连
        if(root.left && root.right){ 
            root.left.next = root.right
        }
    	// 非同一父节点的左右节点相连
        if(root.right && root.next && root.next.left){ 
            root.right.next = root.next.left
        }
    	// 递归遍历
        connect(root.left)
        connect(root.right)
        return root
    };

#### 提交结果 ####

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

[20200823004749733.png]: /images/20221124/e71d213cecbc44049e9aa52649413825.png?
[20200823004516272.png]: /images/20221124/fbbb9e4a4fdf46e5a86e2efa811a6e0d.png?