題目:

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

給定一個binary tree,依後序遍歷(Postorder 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 postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        if not root: #防範一開始給的root就是None
            return []
        
        ans=[]
        
        def dfs(root,ans):
            if root.left!=None: #先拜訪左節點
                dfs(root.left,ans)
            
            if root.right!=None: #再拜訪右節點
                dfs(root.right,ans)
            
            ans.append(root.val) #最後拜訪父節點
                
            return ans     
        return dfs(root,ans)

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

一如往常,題目下面留下了挑戰

Recursive solution is trivial, could you do it iteratively?

老樣子,我們開始吧

# 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 postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        if not root: #防範一開始給的root就是None
            return []
            
        ans=[]
        path=[]
        
        while True:
            if root.left: #左有枝往左探勘
                path.append(root) #將node紀錄到path內,以便回傳
                root=root.left
                
            elif root.right: #右有枝往右探勘
                path.append(root) #將node紀錄到path內,以便回傳
                root=root.right
                
            else:
                ans.append(root.val) #無枝可探勘則紀錄值
                
                if path==[]: #完全遍歷,結束程式
                    return ans
                    
                root=path.pop() #完全探索完,回上一節點
                
                if root.left: #回來若左枝在則切左枝,因為左枝在則代表我們是探索完左枝回來的
                    root.left=None
                else: #回來若左枝不在則切右枝,因為左枝不在則代表我們是探索完右枝回來的
                    root.right=None

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

上述都跟94.相似
比較不一樣的點是紀錄順序變更
且這次切枝左右都需切枝
因為要確認左右兩枝的值都已紀錄過or無左右兩枝才能紀錄父節點的值(最後紀錄父節點)
最後執行時間27ms(faster than 97.28%)

那我們下題見