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

题目描述

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

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

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

要求使用常量级额外空间。（递归工作栈不算，可以递归）

解题思路

第一反应思路：python

def connect(self, root: 'Node') -> 'Node':
        from collections import deque
        if not root: return root
        queue = deque()
        queue.appendleft(root)
        while queue:
            p = None
            n = len(queue)
            for _ in range(n):
                tmp = queue.pop()
                if p:
                    p.next = tmp
                    p = p.next
                else:
                    p = tmp
                if tmp.left:
                    queue.appendleft(tmp.left)
                if tmp.right:
                    queue.appendleft(tmp.right)
            p.next = None 
        return root

但是不满足空间复杂度要求（但是这种方法非常好理解），所以我们需要改用其他方法。

主要有递归和非递归两种方法，参考题解。

递归：python

def connect(self, root: 'Node') -> 'Node':
        if not root:
            return 
        if root.left:
            root.left.next = root.right
            if root.next:
                root.right.next = root.next.left
        self.connect(root.left)
        self.connect(root.right)
        return root

非递归：java

public Node connect(Node root) {
    if (root == null)
        return root;
    Node cur = root;
    Node pre = null;
    while (cur != null) {
        while (pre != null) {
            pre.left.next = pre.right;
            if (pre.next != null)
                pre.right.next = pre.next.left;
            pre = pre.next;
        }
        pre = cur;
        cur = cur.left;
    }

    return root;
}

参考代码

拉拉链解法：c++

// 拉拉链解法，非常优雅、简洁。
class Solution {
public:
    Node* connect(Node* root) {
        if(root == nullptr) 
            return nullptr;
        Node* left = root->left;
        Node* right = root->right;
        while(left && right) {
            left->next = right;
            left = left->right;
            right = right->left;
        }
        connect(root->left);
        connect(root->right);
        return root;
    }
    
};