Commit54eb762

committed

add populating next right pointers ii

1 parentc976fdc commit54eb762Copy full SHA for 54eb762

File tree

+28

-2

lines changed

+28

-2

lines changed

Lines changed: 28 additions & 2 deletions

Original file line number	Diff line number	Diff line change
`@@ -1,4 +1,30 @@`
	`1`	`+##Improved version of[Populating Next Right Pointers in Each Node](../populating-next-right-pointers-in-each-node)`
`1`	`2`
`2`		`-##TODO`
`3`		`-* write down thinking`
	`3`	`+This time, finding next is a bit difficult.`
	`4`	+`node.right.next = node.next.left` is no longer working.
`4`	`5`
	`6`	`+But parent's next is also useful, and only need to seach a little more nodes.`
	`7`	`+`
	`8`	+```
	`9`	`+ 1`
	`10`	`+ / \`
	`11`	`+ 2 3`
	`12`	`+ \ \`
	`13`	`+ 4 5`
	`14`	`+ / / \`
	`15`	`+ 6 7 8`
	`16`	+```
	`17`	`+`
	`18`	+*`6.next` =`7` =`5.left` =`4.next.left`
	`19`	+*`4.next` =`5` =`3.right` =`2.next.right`
	`20`	`+`
	`21`	`+Searching path is like`
	`22`	`+`
	`23`	`+* node's parent's left`
	`24`	`+* node's parent's right`
	`25`	`+* take node's parent's next as parent and search again`
	`26`	`+`
	`27`	`+`
	`28`	`+Note:`
	`29`	`+`
	`30`	+`connect(right)` before`connect(left)`, because`left nodes` depend on`right nodes' next`

Comments

(0)