|
3 | 3 | importjava.util.LinkedList; |
4 | 4 | importjava.util.Queue; |
5 | 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 | + */ |
6 | 14 | publicclassConnect2 { |
7 | | -publicvoidconnect(TreeLinkNoderoot) { |
| 15 | +/* |
| 16 | + Solution 1: space: O(N), the nodes of the last level. |
| 17 | + */ |
| 18 | +publicvoidconnect1(TreeLinkNoderoot) { |
8 | 19 | if (root ==null) { |
9 | 20 | return; |
10 | 21 | } |
@@ -38,6 +49,101 @@ public void connect(TreeLinkNode root) { |
38 | 49 | q.offer(cur.right); |
39 | 50 | } |
40 | 51 | } |
| 52 | + } |
| 53 | + |
| 54 | +/* |
| 55 | + Solution 2: recursion with O(h) space. H: the height of the tree. |
| 56 | + */ |
| 57 | +publicvoidconnect2(TreeLinkNoderoot) { |
| 58 | +if (root ==null) { |
| 59 | +return; |
| 60 | + } |
41 | 61 |
|
| 62 | +TreeLinkNodecur =root.next; |
| 63 | +TreeLinkNodenext =null; |
| 64 | +// this is very important. should exit after found the next. |
| 65 | +while (cur !=null &&next ==null) { |
| 66 | +if (cur.left !=null) { |
| 67 | +next =cur.left; |
| 68 | + }elseif (cur.right !=null) { |
| 69 | +next =cur.right; |
| 70 | + }else { |
| 71 | +cur =cur.next; |
| 72 | + } |
| 73 | + } |
| 74 | + |
| 75 | +if (root.right !=null) { |
| 76 | +root.right.next =next; |
| 77 | +next =root.right; |
| 78 | + } |
| 79 | + |
| 80 | +if (root.left !=null) { |
| 81 | +root.left.next =next; |
| 82 | + } |
| 83 | + |
| 84 | +// The order is very important. We should deal with right first! |
| 85 | +connect2(root.right); |
| 86 | +connect2(root.left); |
| 87 | + } |
| 88 | + |
| 89 | +/* |
| 90 | + Solution 3: iterator with O(1) space. |
| 91 | + */ |
| 92 | +publicvoidconnect(TreeLinkNoderoot) { |
| 93 | +if (root ==null) { |
| 94 | +return; |
| 95 | + } |
| 96 | + |
| 97 | +connIterator(root); |
| 98 | + } |
| 99 | + |
| 100 | +/* |
| 101 | + This is a iterator version. |
| 102 | + */ |
| 103 | +publicvoidconnIterator(TreeLinkNoderoot) { |
| 104 | +TreeLinkNodeleftEnd =root; |
| 105 | +while (leftEnd !=null) { |
| 106 | +TreeLinkNodep =leftEnd; |
| 107 | + |
| 108 | +// Connect all the nodes in the next level together. |
| 109 | +while (p !=null) { |
| 110 | + |
| 111 | +// find the |
| 112 | +TreeLinkNodenext =findLeftEnd(p.next); |
| 113 | + |
| 114 | +if (p.right !=null) { |
| 115 | +p.right.next =next; |
| 116 | +next =p.right; |
| 117 | + } |
| 118 | + |
| 119 | +if (p.left !=null) { |
| 120 | +p.left.next =next; |
| 121 | + } |
| 122 | + |
| 123 | +// continue to deal with the next point. |
| 124 | +p =p.next; |
| 125 | + } |
| 126 | + |
| 127 | +// Find the left end of the NEXT LEVEL. |
| 128 | +leftEnd =findLeftEnd(leftEnd); |
| 129 | + } |
| 130 | + |
| 131 | + } |
| 132 | + |
| 133 | +// Find out the left end of the next level of Root TreeNode. |
| 134 | +publicTreeLinkNodefindLeftEnd(TreeLinkNoderoot) { |
| 135 | +while (root !=null) { |
| 136 | +if (root.left !=null) { |
| 137 | +returnroot.left; |
| 138 | + } |
| 139 | + |
| 140 | +if (root.right !=null) { |
| 141 | +returnroot.right; |
| 142 | + } |
| 143 | + |
| 144 | +root =root.next; |
| 145 | + } |
| 146 | + |
| 147 | +returnnull; |
42 | 148 | } |
43 | 149 | } |