1+ package Algorithms .tree ;
2+
3+ import java .util .LinkedList ;
4+ import java .util .Queue ;
5+
6+ /**
7+ * Definition for binary tree with next pointer.
8+ * public class TreeLinkNode {
9+ * int val;
10+ * TreeLinkNode left, right, next;
11+ * TreeLinkNode(int x) { val = x; }
12+ * }
13+ */
14+ public class Connect_2014_1229 {
15+ /*
16+ 1. Iterator.
17+ */
18+ public void connect1 (TreeLinkNode root ) {
19+ if (root ==null ) {
20+ return ;
21+ }
22+
23+ Queue <TreeLinkNode >q =new LinkedList <TreeLinkNode >();
24+ q .offer (root );
25+
26+ while (!q .isEmpty ()) {
27+ int size =q .size ();
28+
29+ for (int i =0 ;i <size ;i ++) {
30+ TreeLinkNode cur =q .poll ();
31+
32+ // ERROR 2: forget to determine if root don't have left and right.
33+ if (cur .left ==null ) {
34+ return ;
35+ }
36+
37+ cur .left .next =cur .right ;
38+ cur .right .next =cur .next ==null ?null :cur .next .left ;
39+ // bug 1: should put the offer inside the for loop
40+ q .offer (cur .left );
41+ q .offer (cur .right );
42+ }
43+ }
44+ }
45+
46+ /*
47+ 2. Iterator. More simple version.
48+ */
49+ public void connect2 (TreeLinkNode root ) {
50+ if (root ==null ) {
51+ return ;
52+ }
53+
54+ Queue <TreeLinkNode >q =new LinkedList <TreeLinkNode >();
55+ q .offer (root );
56+
57+ while (!q .isEmpty ()) {
58+ int size =q .size ();
59+
60+ for (int i =0 ;i <size ;i ++) {
61+ TreeLinkNode cur =q .poll ();
62+
63+ // bug 1: should judge the size!
64+ cur .next = (i ==size -1 ) ?null :q .peek ();
65+
66+ if (cur .left !=null ) {
67+ q .offer (cur .left );
68+ q .offer (cur .right );
69+ }
70+ }
71+ }
72+ }
73+
74+ /*
75+ 3. A recursion version.
76+ */
77+ public void connect3 (TreeLinkNode root ) {
78+ if (root ==null ||root .left ==null ) {
79+ return ;
80+ }
81+
82+ root .left .next =root .right ;
83+ root .right .next =root .next ==null ?null :root .next .left ;
84+
85+ connect (root .left );
86+ connect (root .right );
87+ }
88+
89+ /*
90+ 4. Another constant iterator version.
91+ */
92+ public void connect (TreeLinkNode root ) {
93+ if (root ==null ) {
94+ return ;
95+ }
96+
97+ TreeLinkNode leftEnd =root ;
98+ while (leftEnd !=null &&leftEnd .left !=null ) {
99+ TreeLinkNode cur =leftEnd ;
100+ while (cur !=null ) {
101+ cur .left .next =cur .right ;
102+ cur .right .next =cur .next ==null ?null :cur .next .left ;
103+
104+ cur =cur .next ;
105+ }
106+
107+ leftEnd =leftEnd .left ;
108+ }
109+ }
110+ }
