# Definition for a binary tree node.
# 前序遍歷的意思是先遍歷根節點，然后遍歷左子樹，最后是右子樹
# 因此這道題可以用遞回的方法直接解出來，
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
from typing import List
class Solution:
def preorderTraversal1(self, root: TreeNode) -> List[int]:
self.res = []
self.dfs(root)
return self.res
def dfs(self,root):
if not root :return
# 先遍歷根節點
self.res.append(root.val)
# 然后遍歷左子樹
self.dfs(root.left)
# 然后是右子樹
self.dfs(root.right)
# 下邊是迭代的方法，
def preorderTraversal(self, root: TreeNode) -> List[int]:
if not root :return []
# 將根節點壓入堆疊
stack,res = [root],[]
# 當堆疊為空的時候，代表所有的節點都遍歷了
while stack:
# 彈出節點
node = stack.pop()
# 判斷節點是否為空
if node:
# 將節點放入串列
res.append(node.val)
# 將右節點壓入堆疊
if node.right :
stack.append(node.right)
# 將左節點壓入堆疊
if node.left :
stack.append(node.left)
return res
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/83294.html
標籤：Python