leetcode链表之二叉树填充右侧节点指针

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

题目：

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

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

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

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

示例1：

输入：root = [1,2,3,4,5,6,7]
输出：[1,#,2,3,#,4,5,6,7,#]

示例2：

输入：root = []
输出：[]

---

思路：

这里其实需要考虑的是二叉树的层遍历，直接上代码了

代码1：

使用数组（栈）来处理

class Solution:
    def connect(self, root: 'Optional[Node]') -> 'Optional[Node]':
        if not root: return root
        stack = [root]
        while stack:
            n = len(stack)
            # 这里通过for控制该层需要遍历的数据，遍历完成后，stack中剩余的就是下一层的数据
            for i in range(n):
                cur = stack.pop(0)
                # 这里判断如果stack中有下一个结点，直接相连即可
                if i < n - 1:
                    cur.next = stack[0]
                # 将下一层的结点放到stack中
                if cur.left:
                    stack.append(cur.left)
                if cur.right:
                    stack.append(cur.right)
        return root

代码2：

站在父节点的角度上将下一层的子节点连起来

class Solution:

    def connect(self, root: 'Optional[Node]') -> 'Optional[Node]':
        if not root: return root
        cur = root
        while cur.left:
            head = cur
            # 这里通过循环遍历同一层的数据，将左右结点连接起来
            while head:
                head.left.next = head.right
                # 这里是看右节点是否需要连接，如果head有next结点，就让右节点和head.next的左节点相连
                if head.next:
                    head.right.next = head.next.left
                head = head.next
            cur = cur.left
        return root

117、填充每个节点的下一个右侧结点指针2

题目：

给定一个二叉树

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

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

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

示例：

输入：root = [1,2,3,4,5,null,7]
输出：[1,#,2,3,#,4,5,7,#]

---

思路：

数组的代码和116的代码一样，这里就不贴了，看一下站在父节点的角度怎么处理吧

class Solution:
    def connect(self, root: 'Node') -> 'Node':
        if not root: return root
        cur = root
        while cur:
            # prev结点缓存子节点的前一个非空结点, first缓存子节点第一个非空结点，用于下一层级的初始化遍历
            prev, first = None, None
            head = cur
            while head:
                # 如果当前head有左节点，看prev是否缓存值，如果缓存了，就说明之前已经有非空结点，那么直接相连即可
                # 此时将head.left缓存起来即可，右节点同理
                if head.left:
                    if prev:
                        prev.next = head.left
                    prev = head.left
                    # 找到第一个非空结点
                    if not first: first = head.left
                if head.right:
                    if prev:
                        prev.next = head.right
                    prev = head.right
                    if not first: first = head.right
                # 当head处理完成后，处理head的next结点
                head = head.next
            cur = next
        return root