leetcode with python:145. Binary Tree Postorder Traversal

题目:

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 = rightclass 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 = rightclass 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%)

那我们下题见