Paste_Image.png
My code:
import java.util.LinkedList;
import java.util.Queue;
/**
* Definition for binary tree with next pointer.
* public class TreeLinkNode {
* int val;
* TreeLinkNode left, right, next;
* TreeLinkNode(int x) { val = x; }
* }
*/
public class Solution {
public void connect(TreeLinkNode root) {
if (root == null)
return;
Queue<TreeLinkNode> q = new LinkedList<TreeLinkNode>();
q.offer(root);
while (!q.isEmpty()) {
int levelSize = q.size();
TreeLinkNode next = null;
for (int i = 0; i < levelSize; i++) {
TreeLinkNode temp = q.poll();
if (i == 0) {
temp.next = null;
next = temp;
}
else {
temp.next = next;
next = temp;
}
if (temp.right != null)
q.offer(temp.right);
if (temp.left != null)
q.offer(temp.left);
}
}
}
}
My test result:
Paste_Image.png
这道题目就是完全用的上道题目的思想。
遍历树有几种方式？
一二三，先序中序后序
四，层序
层序分为两种，
从左到右和从右到左。
**
总结： 右层序遍历tree
**
Anyway, Good luck, Richardo!
My code:
/**
* Definition for binary tree with next pointer.
* public class TreeLinkNode {
* int val;
* TreeLinkNode left, right, next;
* TreeLinkNode(int x) { val = x; }
* }
*/
public class Solution {
public void connect(TreeLinkNode root) {
if (root == null)
return;
Queue<TreeLinkNode> q = new LinkedList<TreeLinkNode>();
q.offer(root);
while (!q.isEmpty()) {
int size = q.size();
TreeLinkNode prev = null;
for (int i = 0; i < size; i++) {
TreeLinkNode curr = q.poll();
if (curr.right!= null) {
curr.right.next = prev;
curr.left.next = curr.right;
prev = curr.left;
q.offer(curr.right);
q.offer(curr.left);
}
else
return;
}
}
return;
}
}
简单题，没什么好说的。层序遍历，右边的先进队列。
My code:
/**
* Definition for binary tree with next pointer.
* public class TreeLinkNode {
* int val;
* TreeLinkNode left, right, next;
* TreeLinkNode(int x) { val = x; }
* }
*/
public class Solution {
public void connect(TreeLinkNode root) {
if (root == null) {
return;
}
Queue<TreeLinkNode> q = new LinkedList<TreeLinkNode>();
q.offer(root);
while (!q.isEmpty()) {
int size = q.size();
TreeLinkNode pre = null;
for (int i = 0; i < size; i++) {
TreeLinkNode curr = q.poll();
curr.next = pre;
pre = curr;
if (curr.right != null) {
q.offer(curr.right);
q.offer(curr.left);
}
}
}
}
}
并不难。
然后网上看到了一种 recursion 做法
自己写了下，充分用到了 perfect tree 的特点
My code:
/**
* Definition for binary tree with next pointer.
* public class TreeLinkNode {
* int val;
* TreeLinkNode left, right, next;
* TreeLinkNode(int x) { val = x; }
* }
*/
public class Solution {
public void connect(TreeLinkNode root) {
if (root != null) {
if (root.left != null) {
root.left.next = root.right;
if (root.next != null) {
root.right.next = root.next.left;
}
}
connect(root.left);
connect(root.right);
}
}
}
真傻逼了，原来题目要求空间开销是 O(1)
所以得这么做：
My code:
/**
* Definition for binary tree with next pointer.
* public class TreeLinkNode {
* int val;
* TreeLinkNode left, right, next;
* TreeLinkNode(int x) { val = x; }
* }
*/
public class Solution {
public void connect(TreeLinkNode root) {
if (root == null) {
return;
}
TreeLinkNode head = root;
TreeLinkNode curr = null;
while (head != null) {
curr = head;
head = curr.left;
while (curr != null) {
if (curr.left != null) {
curr.left.next = curr.right;
if (curr.next != null) {
curr.right.next = curr.next.left;
}
}
curr = curr.next;
}
}
}
}
Anyway, Good luck, Richardo! -- 09/06/2016
