算法導(dǎo)論 p.248 10.4-4
題目描述：對(duì)于一個(gè)含n個(gè)結(jié)點(diǎn)的任意有根樹，寫出一個(gè)O(n)時(shí)間的過程涵紊，輸出其所有關(guān)鍵字哈街，該樹以左孩子右兄弟表示法存儲(chǔ)。
與二叉樹的遍歷類似
- 樹結(jié)構(gòu)的定義：
class Tree:
def __init__(self, val):
self.val = val
self.left_child = None
self.right_bro = None
- 使用棧實(shí)現(xiàn)了樹的遍歷
class Solution:
def getAllNodeFromTreeByStack(self, tree=Tree) -> List[int]:
if not self:
return []
resList, stack = [], list()
stack.append(self)
while stack:
node = stack.pop()
resList.append(node.val)
if node.right_bro:
stack.append(node.right_bro)
if node.left_child:
stack.append(node.left_child)
return resList
- 使用隊(duì)列實(shí)現(xiàn)了樹的遍歷
class Solution:
def getAllNodeFromTreeByQueue(self, tree=Tree) -> List[int]:
if not self:
return []
resList, queue = [], collections.deque()
queue.append(self)
while queue:
node = queue.popleft()
resList.append(node.val)
if node.right_bro:
queue.append(node.right_bro)
if node.left_child:
queue.append(node.left_child)
return resList
- 使用遞歸實(shí)現(xiàn)了樹的遍歷
class Solution:
def getAllNodeFromTreeByRecursion(self, tree=Tree) -> List[int]:
if not self:
return []
resList = []
if tree:
resList.append(tree.val)
if tree.right_bro:
resList.extend(Solution.getAllNodeFromTreeByRecursion(self=self, tree=tree.right_bro))
if tree.left_child:
resList.extend(Solution.getAllNodeFromTreeByRecursion(self=self, tree=tree.left_child))
return resList
- 驗(yàn)證
if __name__ == '__main__':
tree = Tree(0)
tree.left_child = Tree(10)
tree.left_child.right_bro = Tree(12)
tree.left_child.right_bro.right_bro = Tree(-1)
tree.left_child.right_bro.right_bro.right_bro = Tree(93)
tree.left_child.right_bro.right_bro.right_bro.left_child = Tree(100)
print(Solution.getAllNodeFromTreeByStack(self=tree, tree=tree)) # [0, 10, 12, -1, 93, 100]
print(Solution.getAllNodeFromTreeByQueue(self=tree, tree=tree)) # [0, 10, 12, -1, 93, 100]
print(Solution.getAllNodeFromTreeByRecursion(self=tree, tree=tree)) # [0, 10, 12, -1, 93, 100]
