update solution

liningrui · liningrui · commit cc2e1143a58e · 2022-07-20T06:43:19.000+08:00
diff --git a/.gitignore b/.gitignore
@@ -1,2 +1,5 @@
+./script/leetcode/*
+.DS_Store
+.idea/
 ./Tmp/*
 Tmp
diff --git a/树/117. 填充每个节点的下一个右侧节点指针 II.md b/树/117. 填充每个节点的下一个右侧节点指针 II.md
@@ -49,23 +49,27 @@ class Node:
 
 class Solution:
     def connect(self, root: 'Node') -> 'Node':
-        if not root:
-            return root
-        stack = [root]
-        while stack:
-            n = len(stack)
-            for i in range(n):
-                node = stack.pop(0)
-                if node.left:
-                    stack.append(node.left)
-                if node.right:
-                    stack.append(node.right)
-                if i==n-1:
-                    node.next = None
-                else:
-                    node.next = stack[0]
-
-        return root 
+        #核心在于常数额外空间，这里的next指针本身就提供了层次便利的可能，每一层构建下一层的next指针然后移动到下一层
+        pre, cur, head = None, root, None
+        while cur:
+            #遍历一行
+            while cur:
+                if cur.left:
+                    if pre:
+                        pre.next= cur.left
+                    else:
+                        head=cur.left #下一行第一个节点
+                    pre = cur.left # 向右移一位/或者创建起始起点
+                if cur.right:
+                    if pre:
+                        pre.next= cur.right
+                    else:
+                        head=cur.right
+                    pre = cur.right# 向右移一位/或者创建起始起点
+                cur = cur.next
+            cur = head
+            head = pre = None
+        return root
 ```
 
-虽然不是完美树，但是对解法并没有影响
+117 和116的差异在于常数空间占用，因为next指针本身提供了横向遍历的可能，所以用3个指针分别指向当前，上一个节点，以及下一行的初始节点

-Original file line number
+Diff line change
@@ @@ -1,2 +1,5 @@ @@
 +./script/leetcode/*
 +.DS_Store
 +.idea/
 ./Tmp/*
 Tmp