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:
<!--more-->
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:
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:
Input: root = []
Output: []
这题我不会,看了解法还是不懂,所以去找了个视频,POPULATING NEXT RIGHT POINTERS IN EACH NODE (Leetcode) - Code & Whiteboard,视频里讲的是 Python 的代码,但是逻辑很清晰,翻译成 Swift 也可以用。
简单理解如下:
代码如下:
/**
* 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
}
}
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。