Algorithem_Populating Next Right Pointers in Each Node

2022-04-21

Algorithem_Populating Next Right Pointers in Each Node

You are given a perfect binary tree where all leaves are on the same level, and every parent has two children. The binary tree has the following definition:

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

Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL.

Initially, all next pointers are set to NULL.

Example 1:

1 2	Input: root = [1,2,3,4,5,6,7] Output: [1,#,2,3,#,4,5,6,7,#]

Explanation: Given the above perfect binary tree (Figure A), your function should populate each next pointer to point to its next right node, just like in Figure B. The serialized output is in level order as connected by the next pointers, with ‘#’ signifying the end of each level.

Example 2:

1 2	Input: root = [] Output: []

解法

这题我不会，看了解法还是不懂，所以去找了个视频，POPULATING NEXT RIGHT POINTERS IN EACH NODE (Leetcode) - Code & Whiteboard，视频里讲的是 Python 的代码，但是逻辑很清晰，翻译成 Swift 也可以用。

简单理解如下：

perfect binary tree，所以有 left 一定有 right，故而遍历时通过判断node.left 是否存在，即可知道是否有下一级
all next pointers are set to NULL，初始时所有node 的 next 都是 nil
同一个父节点left 和 right 设置 next 关系，即 node.left.next = node.right，比如2和3、4和5、6和7
不同父节点的设置 next 关系，则需要判断父节点的 next 是否存在，存在则设置 node.right.next = node.next.left，比如5和6

代码如下：


/**
 * Definition for a Node.
 * public class Node {
 *     public var val: Int
 *     public var left: Node?
 *     public var right: Node?
 *	   public var next: Node?
 *     public init(_ val: Int) {
 *         self.val = val
 *         self.left = nil
 *         self.right = nil
 *         self.next = nil
 *     }
 * }
 */

class Solution {
    func connect(_ root: Node?) -> Node? {
        // error check
        if root == nil {
            return nil
        }
        
        var leftMostNode = root
        // loop left
        while (leftMostNode?.left != nil) {
            var cur = leftMostNode
            while (cur?.left != nil) {
                cur?.left?.next = cur?.right
                if (cur?.next != nil) {
                    cur?.right?.next = cur?.next?.left
                }
                cur = cur?.next
            }
            leftMostNode = leftMostNode?.left
        }
        return root
    }
}