前序遍历(递归)
class Solution: def preorder(self,root): if not root: return [] return [root.val] + [self.preorder(root.left)] + [self.preorder(root.right)]
中序遍历(递归)
class Solution: def middleorder(self,root): if not root: return [] return [self.middleorder(root.left)] + [root.val] + [self.middleorder(root.right)]
后序遍历(递归)
class Solution: def postorder(self,root): if not root: return [] return [self.postorder(root.left)] + [self.postorder(root.right)]+[root.val]
前序遍历(非递归)
class Solution: def preorder(self,root): if root is None: return [] stack = [root] res = [] while stack: node = stack.pop() if node is not None: res.append(node.val) if node.right is not None: stack.append(node.right) if node.left id not None: stack.append(node.left) return res
中序遍历(非递归)
class Solution: def middleorder(self,root): res = [] stack = [] while stack or root: while root: stack.append(root) root = root.left root= stack.pop() res.append(root.val) root = root.right return res
层序遍历(非递归)
class Solution: def levelorder(self,root): if root is None: return [] res = [] queue= [root] while queue: level = [] for _ in range(len(queue)): node = queue.pop(0) level.append(node.val) if node.left: queue.append(node.left) if node.right: queue.append(node.right) res.append(level) return res