leetcode with python:94. Binary Tree Inorder Traversal

题目:

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

给定一个binary tree,依中序遍历(Inorder Traversal)的顺序回传里面的值(用list)

到这里,可能要先讲一下二元树(binary tree)
二元树是长这样的资料结构

一个node最多只能有两个子node(left,right),最上层的node称root,无子节点的node称leaf
一种相当着名且重要的资料结构

认识二元树很快,但真正需要时间理解及熟练的是它的搜寻法
分为两种:深度优先搜寻(DFS)和广度优先搜寻(BFS)

深度优先搜寻如其名,儘可能深入地探索树的分支,当所在node所接的node都被探索过,就再返回上一个node,重複执行
以图来看的话就是长这样

广度优先搜寻是即把同一层的node走访完，再继续向下一层搜寻，直到遍寻全部node
以图来看的话就是长这样

两种方式在以后的程式都会用到,会特别提

接着是遍历顺序,主要分三种前序遍历(Preorder Traversal),中序遍历(Inorder Traversal),后序遍历(Postorder Traversal)
前序遍历:先拜访父节点再拜访左右子节点
中序遍历:先拜访左子节点，再拜访父节点，最后拜访右子节点
后序遍历:先拜访左右子节点，最后拜访父节点

那我们回到题目,这题我是用dfs下去做

# 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 inorderTraversal(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)                            ans.append(root.val) #再拜访父节点                        if root.right!=None: #最后拜访右节点                dfs(root.right,ans)                            return ans #全拜访过后回传上一节点                    return dfs(root,ans)

以递迴的方式走访,且设一个空list存走访的值
如上面的dfs定义,透过递迴的方式深入探索树的分支
依中序遍历的方式向深处走访,完全走访完回到上一节点,不断重複
完全跑完后就获得我们要的阵列了
最后执行时间28ms(faster than 96.22%)

但是到这里题目还没结束,最下面写了一行

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 inorderTraversal(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: #右有枝往右探勘                ans.append(root.val) #由于是中序遍历,要先纪录父节点值                root=root.right      #又因为右枝探勘完就等于这个node已完全纪录,故不存在path内                            else:                ans.append(root.val) #到底端纪录值                                if path==[]: #完全遍历,结束程式                    return ans                                    root=path.pop() #完全探索完,回上一节点                                if root.left: #回来若左枝在则切左枝,因为左枝在则代表我们是探索完左枝回来的                    root.left=None  

设两个空阵列,一个纪录走访值(ans),一个纪录当一个node走访完毕后要回传的node(path)
又由于我是以模拟dfs的搜索方式,path会以stack的方式去做纪录和取出(后进先出)
记得左边的枝探索完要记得切枝(把探索完的枝变None)才可以让程式换边去探索(左枝完换右枝)
最后当path内没东西,且也没有枝可以探索的时候,就代表我们已经完全遍历
由于这个程式实在有点难口述,所以主要资讯我都打在注解上
最后执行时间29ms(faster than 95.29%)

本题学习到的重点:二元树(Binary Tree),深度优先搜寻(DFS),广度优先搜寻(BFS)
那我们下题见