leetcode with python:144. Binary Tree Preorder Traversal

题目:

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

那我们下题见