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

Time: 20190901
Type: Medium

题目描述

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

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

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

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/populating-next-right-pointers-in-each-node
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

由于是满二叉树，可以用递归的思路来解，左孩子的next指向是右孩子，右孩子的指向是父节点的next指向的左孩子。且满足递归的性质。和117还不太一样，117和本题都可以用队列来解。

代码

'''
# Definition for a Node.

class Node:
    def __init__(self, val, left, right, next):
        self.val = val
        self.left = left
        self.right = right
        self.next = next
'''

class Solution:
    def connect(self, root: 'Node') -> 'Node':
        if not root:
            return 
        # 左孩子的next指向右孩子
        if root.left:
            root.left.next = root.right
            
        if root.right and root.next:
            root.right.next = root.next.left
            
        self.connect(root.left)
        self.connect(root.right)
        
        return root

END.