Commitc4b1aec

committed

connect

1 parent399814b commitc4b1aecCopy full SHA for c4b1aec

File tree

+73

-1

lines changed

+73

-1

lines changed

Lines changed: 30 additions & 1 deletion

Original file line number	Diff line number	Diff line change
`@@ -12,7 +12,10 @@`
`12`	`12`	`* }`
`13`	`13`	`*/`
`14`	`14`	`publicclassConnect {`
`15`		`-publicvoidconnect(TreeLinkNoderoot) {`
	`15`	`+/*`
	`16`	`+ * 使用level traversal来做。`
	`17`	`+ * */`
	`18`	`+publicvoidconnect1(TreeLinkNoderoot) {`
`16`	`19`	`if (root ==null) {`
`17`	`20`	`return;`
`18`	`21`	`}`
`@@ -46,4 +49,30 @@ public void connect(TreeLinkNode root) {`
`46`	`49`	`}`
`47`	`50`	`}`
`48`	`51`	`}`
	`52`	`+`
	`53`	`+/* 试一下 recursion */`
	`54`	`+publicvoidconnect(TreeLinkNoderoot) {`
	`55`	`+if (root ==null) {`
	`56`	`+return;`
	`57`	`+ }`
	`58`	`+`
	`59`	`+rec(root);`
	`60`	`+ }`
	`61`	`+`
	`62`	`+publicvoidrec(TreeLinkNoderoot) {`
	`63`	`+if (root ==null) {`
	`64`	`+return;`
	`65`	`+ }`
	`66`	`+`
	`67`	`+if (root.left !=null) {`
	`68`	`+root.left.next =root.right;`
	`69`	`+ }`
	`70`	`+`
	`71`	`+if (root.right !=null) {`
	`72`	`+root.right.next =root.next.left;`
	`73`	`+ }`
	`74`	`+`
	`75`	`+rec(root.left);`
	`76`	`+rec(root.right);`
	`77`	`+ }`
`49`	`78`	`}`

Lines changed: 43 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -0,0 +1,43 @@`
	`1`	`+packageAlgorithms.tree;`
	`2`	`+`
	`3`	`+importjava.util.LinkedList;`
	`4`	`+importjava.util.Queue;`
	`5`	`+`
	`6`	`+publicclassConnect2 {`
	`7`	`+publicvoidconnect(TreeLinkNoderoot) {`
	`8`	`+if (root ==null) {`
	`9`	`+return;`
	`10`	`+ }`
	`11`	`+`
	`12`	`+TreeLinkNodedummy =newTreeLinkNode(0);`
	`13`	`+Queue<TreeLinkNode>q =newLinkedList<TreeLinkNode>();`
	`14`	`+`
	`15`	`+q.offer(root);`
	`16`	`+q.offer(dummy);`
	`17`	`+`
	`18`	`+while(!q.isEmpty()) {`
	`19`	`+TreeLinkNodecur =q.poll();`
	`20`	`+if (cur ==dummy) {`
	`21`	`+if (!q.isEmpty()) {`
	`22`	`+q.offer(dummy);`
	`23`	`+ }`
	`24`	`+continue;`
	`25`	`+ }`
	`26`	`+`
	`27`	`+if (q.peek() ==dummy) {`
	`28`	`+cur.next =null;`
	`29`	`+ }else {`
	`30`	`+cur.next =q.peek();`
	`31`	`+ }`
	`32`	`+`
	`33`	`+if (cur.left !=null) {`
	`34`	`+q.offer(cur.left);`
	`35`	`+ }`
	`36`	`+`
	`37`	`+if (cur.right !=null) {`
	`38`	`+q.offer(cur.right);`
	`39`	`+ }`
	`40`	`+ }`
	`41`	`+`
	`42`	`+ }`
	`43`	`+}`

Comments

(0)