116 Populating Next Right Pointers in Each Node
116. Populating Next Right Pointers in Each Node
1. Question
Given a binary tree
struct TreeLinkNode {
TreeLinkNode *left;
TreeLinkNode *right;
TreeLinkNode *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 toNULL
.
Initially, all next pointers are set toNULL
.
Note:
You may only use constant extra space.
You may assume that it is a perfect binary tree (ie, all leaves are at the same level, and every parent has two children).
For example, Given the following perfect binary tree,
1
/ \
2 3
/ \ / \
4 5 6 7
After calling your function, the tree should look like:
1 ->NULL
/ \
2 -> 3 ->NULL
/ \ / \
4->5->6->7 ->NULL
2. Implementation
(1) Recursion
public class Solution {
public void connect(TreeLinkNode root) {
if (root == null) {
return;
}
if (root.left != null) {
root.left.next = root.right;
if (root.next != null && root.right != null) {
root.right.next = root.next.left;
}
}
connect(root.left);
connect(root.right);
}
}
(2) Iteration
public class Solution {
public void connect(TreeLinkNode root) {
if (root == null) {
return;
}
TreeLinkNode curNode = root;
TreeLinkNode leftMostNode = null;
while (curNode.left != null) {
leftMostNode = curNode.left;
while (curNode != null) {
curNode.left.next = curNode.right;
curNode.right.next = curNode.next == null ? null : curNode.next.left;
curNode = curNode.next;
}
curNode = leftMostNode;
}
}
}
3. Time & Space Complexity
Recursion: 时间复杂度: O(n), 空间复杂度: O(h)
Iteration: 时间复杂度: O(n), 空间复杂度: O(1)
Previous114 Flatten Binary Tree to Linked ListNext117 Populating Next Right Pointers in Each Node II
Last updated
Was this helpful?