題目:

Given the root of a binary tree, return the preorder traversal of its nodes' values.

給定一個binary tree,依前序遍歷(Preorder Traversal)的順序回傳裡面的值(用list)

這題完全就是94.的延伸
程式碼幾乎完全一樣,只要稍微改一下紀錄順序就好

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        if not root: #防範一開始給的root就是None
            return []
        
        ans=[]
        
        def dfs(root,ans):
            ans.append(root.val) #先拜訪父節點
            
            if root.left!=None: #再拜訪左節點
                dfs(root.left,ans)
                
            if root.right!=None: #最後拜訪右節點
                dfs(root.right,ans)
                
            return ans 
            
        return dfs(root,ans)

和94.一樣以遞迴的方式走訪,並設一個空list存走訪的值
不過這次是依中序遍歷的方式走訪,順序不太一樣
一樣一個節點完全走訪後回到上一節點,不斷重複
執行完成後就獲得我們要的陣列了
最後執行時間30ms(faster than 94.29%)

不過跟它的姊妹題一樣,下面留了一段話

Recursive solution is trivial, could you do it iteratively?

OK,here we go again

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        if not root: #防範一開始給的root就是None
            return []
            
        ans=[]
        path=[]
        
        while True:
            if root.val==None: #先紀錄父節點
                ans.append(root.val)
                
            if root.left: #左有枝往左探勘
                path.append(root) #將node紀錄到path內,以便回傳
                root=root.left
                
            elif root.right: #右有枝往右探勘
                root=root.right      #又因為右枝探勘完就等於這個node已完全紀錄,故不存在path內
                
            else:
                if path==[]: #完全遍歷,結束程式
                    return ans
                    
                root=path.pop() #完全探索完,回上一節點
                root.val=None #做記號讓程式不要再記錄一次值
                
                if root.left: #回來若左枝在則切左枝,因為左枝在則代表我們是探索完左枝回來的
                    root.left=None

同樣設兩個空陣列,一個紀錄走訪值(ans),一個紀錄當一個node走訪完畢後要回傳的node(path)
path同樣以stack的方式去做紀錄和取出(後進先出)
左邊的枝探索完要記得切枝(把探索完的枝變None)才可以讓程式換邊去探索(左枝完換右枝)
最後當path內沒東西,且也沒有枝可以探索的時候,就代表我們已經完全遍歷

上述都跟94.相似
比較不一樣的點是紀錄順序變更
且當從path取節點時,將值改為None
因為裡面的值都已紀錄過(先紀錄父節點),因此需做記號讓程式不要再記錄一次
最後執行時間31ms(faster than 92.34%)

那我們下題見