l******r
发帖数: 1 | 5 用3个stack
前两个得倒postorder的顺序，然后从postorder stack里面一个node一个node取，
convert之后再放入stack。
python 代码
------------
from __future__ import annotations
from typing import List
class NodeTypeA:
def __init__(self, payload: str, children : List[NodeTypeA] = []):
self.payload = payload
self.children = children
class NodeTypeB:
def __init__(self, payload: str, children : List[NodeTypeB] = []):
self.payload = payload
self.children = children
def convertLeaf(node: NodeTypeA)->NodeTypeB:
print(f"Converting Leaf NodeTypeA {node.payload}")
return NodeTypeB(node.payload)
def convertParent(node: NodeTypeA, childrenB: List[NodeTypeB])->NodeTypeB:
print(f"Converting Parent NodeTypeA {node.payload}")
return NodeTypeB(node.payload, children = childrenB)
class Solution:
def convert(self, node: NodeTypeA)->None:
if node == None:
return
if len(node.children) == 0:
convertLeaf(node)
return
childrenB = []
for child in node.children:
childrenB.append(self.convert(child))
convertParent(node, childrenB)
return
def convert_iterative(self, node:NodeTypeA)->None:
stack = []
stack.append(node)
postorder_stack = []
while stack:
node = stack.pop()
postorder_stack.append(node)
for child in node.children:
stack.append(child)
child_stack = []
while postorder_stack:
node = postorder_stack.pop()
if len(node.children) == 0:
child_stack.append(convertLeaf(node))
else:
size = len(node.children)
nodeBs = []
while size > 0:
nodeBs.append(child_stack.pop())
size -= 1
child_stack.append(convertParent(node, nodeBs[::-1]))
return
if __name__ == "__main__":
n1 = NodeTypeA(1)
n2 = NodeTypeA(2)
n3 = NodeTypeA(3)
n4 = NodeTypeA(4)
n5 = NodeTypeA(5)
n6 = NodeTypeA(6)
n7 = NodeTypeA(7)
n8 = NodeTypeA(8)
n9 = NodeTypeA(9)
n10 = NodeTypeA(10)
n11 = NodeTypeA(11)
n12 = NodeTypeA(12)
n13 = NodeTypeA(13)
n1.children = [n2, n3, n4]
n2.children = [n5, n6]
n4.children = [n7, n8, n9]
n5.children = [n10]
n6.children = [n11, n12, n13]
sol = Solution()
sol.convert_iterative(n1)
【在 b********n 的大作中提到】
: 贴在了stackoverflow上， 今天面某大厂被问的
: https://stackoverflow.com/questions/71273541/convert-a-n-ary-tree-from-
: bottom-up-without-recursion
|
