算法随笔-二叉树遍历的N种姿势

最近在练习用Python刷算法，leetcode上刷了快300题。一开始怀疑自己根本不会写代码，现在觉得会写一点点了，痛苦又充实的刷题历程。对我这种半路出家的人而言，收获真的很大。

今天就从二叉树遍历写起，曾经有次面试就被迭代实现卡过。。。

 

 

最简单的递归

#先序遍历 def preorderTraversal(self, root: TreeNode) -> List[int]: res=[] def preTraversal(node,result): if node==None: return #输出放在最前 result.append(node.val) preTraversal(node.left,result) preTraversal(node.right,result) preTraversal(root,res) return res #中序遍历 def inorderTraversal(self, root: TreeNode) -> List[int]: res=[] def inorderTraversal(node,result): if node==None: return inorderTraversal(node.left,result) #输出放在中间 result.append(node.val) inorderTraversal(node.right,result) inorderTraversal(root,res) return res #后序遍历 def postorderTraversal(self, root: TreeNode) -> List[int]: res=[] def postTraversal(node,result): if node==None: return postTraversal(node.left,result) postTraversal(node.right,result) #输出放在最后 result.append(node.val) postTraversal(root,res) return res