Commitcc2e114

liningrui

committed

update solution

1 parentef7e407 commitcc2e114Copy full SHA for cc2e114

File tree

+25

-18

lines changed

+25

-18

lines changed

Lines changed: 3 additions & 0 deletions

Lines changed: 22 additions & 18 deletions

Original file line number	Diff line number	Diff line change
`@@ -49,23 +49,27 @@ class Node:`
`49`	`49`
`50`	`50`	`classSolution:`
`51`	`51`	`defconnect(self,root:'Node') ->'Node':`
`52`		`-ifnot root:`
`53`		`-return root`
`54`		`- stack= [root]`
`55`		`-while stack:`
`56`		`- n=len(stack)`
`57`		`-for iinrange(n):`
`58`		`- node= stack.pop(0)`
`59`		`-if node.left:`
`60`		`- stack.append(node.left)`
`61`		`-if node.right:`
`62`		`- stack.append(node.right)`
`63`		`-if i==n-1:`
`64`		`- node.next=None`
`65`		`-else:`
`66`		`- node.next= stack[0]`
`67`		`-`
`68`		`-return root`
	`52`	`+#核心在于常数额外空间，这里的next指针本身就提供了层次便利的可能，每一层构建下一层的next指针然后移动到下一层`
	`53`	`+ pre, cur, head=None, root,None`
	`54`	`+while cur:`
	`55`	`+#遍历一行`
	`56`	`+while cur:`
	`57`	`+if cur.left:`
	`58`	`+if pre:`
	`59`	`+ pre.next= cur.left`
	`60`	`+else:`
	`61`	`+ head=cur.left#下一行第一个节点`
	`62`	`+ pre= cur.left# 向右移一位/或者创建起始起点`
	`63`	`+if cur.right:`
	`64`	`+if pre:`
	`65`	`+ pre.next= cur.right`
	`66`	`+else:`
	`67`	`+ head=cur.right`
	`68`	`+ pre= cur.right# 向右移一位/或者创建起始起点`
	`69`	`+ cur= cur.next`
	`70`	`+ cur= head`
	`71`	`+ head= pre=None`
	`72`	`+return root`
`69`	`73`	```
`70`	`74`
`71`		`-虽然不是完美树，但是对解法并没有影响`
	`75`	`+117 和116的差异在于常数空间占用，因为next指针本身提供了横向遍历的可能，所以用3个指针分别指向当前，上一个节点，以及下一行的初始节点`

Comments

(0)