Brush the topic-BinaryTree
大家好，这是Brush the topic的第一章节,BinaryTree。首先我说一下为什么把这个放在刷题的第一节呢？
原因如下:
- 培养、训练自己的计算机的思维。
- 锻炼模版化，抽象化思维
下面让我们一起去完成一个壮举，那就是完全解决二叉树的遍历问题，以及相关问题。are you ok？
知识点回顾
二叉树的遍历
由于对于二叉树的遍历顺序不同，构造出三种不同的遍历方式
- 前序遍历-根左右
- 中序遍历-左根右
- 后序遍历-左右根
递归代码模版如下
Python
1# Definition for a binary tree node. 2# class TreeNode: 3# def __init__(self, val=0, left=None, right=None): 4# self.val = val 5# self.left = left 6# self.right = right 7 8# 前序遍历 9def preOreder(self, root): 10 if root: 11 self.traverse_path.append(root.val) 12 preOreder(self.left) 13 preOreder(self.right) 14 15# 中序遍历 16def inOreder(self, root): 17 if root: 18 preOreder(self.left) 19 self.traverse_path.append(root.val) 20 preOreder(self.right) 21 22# 后序遍历 23def postOreder(self, root): 24 if root: 25 preOreder(self.left) 26 preOreder(self.right) 27 self.traverse_path.append(root.val)
Golang
1// 前序遍历 2func preOreder(root *TreeNode) { 3 result := []int{} 4 if root == nil {return} 5 result = append(result, root.value) 6 preOreder(root.Left) 7 preOreder(root.Right) 8} 9 10// 中序遍历 11func inOreder(root *TreeNode) { 12 result := []int{} 13 if root == nil {return} 14 preOreder(root.Left) 15 result = append(result, root.value) 16 preOreder(root.Right) 17} 18 19 20// 后序遍历 21func postOreder(root *TreeNode) { 22 result := []int{} 23 if root == nil {return} 24 postOreder(root.Left) 25 postOreder(root.Right) 26 result = append(result, root.value) 27}
practice
基于此我们可以拿下以下题目,完全二叉树递归模版解题
144. 二叉树的前序遍历-Python
Recursive
1# Definition for a binary tree node. 2# class TreeNode: 3# def __init__(self, val=0, left=None, right=None): 4# self.val = val 5# self.left = left 6# self.right = right 7 8# Recursive-1 9class Solution: 10 def preorderTraversal(self, root: TreeNode) -> List[int]: 11 result = [] 12 self.helper(root, result) 13 return result 14 15 def helper(self, root, result): 16 if root is None: return 17 result.append(root.val) 18 self.helper(root.left,result) 19 self.helper(root.right, result) 20# Recursive-2 Another way Anonymous function 21class Solution: 22 def preorderTraversal(self, root: TreeNode) -> List[int]: 23 def helper(root: TreeNode): 24 if not root: return 25 res.append(root.val) 26 helper(root.left) 27 helper(root.right) 28 29 res = list() 30 helper(root) 31 return res 32 33# Recursive-3 more clean code 34class Solution: 35 def preorderTraversal(self, root: TreeNode) -> List[int]: 36 if not root:return [] 37 res = [] 38 res.append(root.val) 39 res+=self.preorderTraversal(root.left) 40 res+=self.preorderTraversal(root.right) 41 return res
Iterative
1# Definition for a binary tree node. 2# class TreeNode: 3# def __init__(self, val=0, left=None, right=None): 4# self.val = val 5# self.left = left 6# self.right = right 7 8# Solution-1 9class Solution1: 10 def preorderTraversal(self, root: TreeNode) -> List[int]: 11 stack, result = [], [] 12 while stack or root: 13 while root: 14 # 前序遍历-根左右，先拿根 15 result.append(root.val) 16 # 压栈 17 stack.append(root) 18 # 拿完根之后拿左儿子 19 root = root.left 20 # 左儿子拿出来，拿右儿子 21 node = stack.pop() 22 root = node.right 23 # # 完成 24 return result 25 26# Solution-2 简化Solution-1 27class Solution2: 28 def preorderTraversal(self, root: TreeNode) -> List[int]: 29 stack, result = [], [] 30 while stack or root: 31 if root: 32 result.append(root.val) 33 stack.append(root) 34 root = root.left 35 else: 36 node = stack.pop() 37 root = node.right 38 return result 39 40# Solution-3 41class Solution3: 42 def preorderTraversal(self, root: TreeNode) -> List[int]: 43 stack, result = [root], [] 44 while stack: 45 # 拿出根 46 node = stack.pop() 47 if node: 48 # 前序遍历拿出，先拿根的值 49 result.append(node.val) 50 # 模仿栈，先入后出。后拿右孩子 51 stack.append(node.right) 52 stack.append(node.left) 53 return result
94. 二叉树的中序遍历-Python
Recursive
1# Definition for a binary tree node. 2# class TreeNode: 3# def __init__(self, val=0, left=None, right=None): 4# self.val = val 5# self.left = left 6# self.right = right 7 8# Recursive-1 9class Solution: 10 def inorderTraversal(self, root: TreeNode) -> List[int]: 11 result = [] 12 self.helper(root, result) 13 return result 14 15 def helper(self, root, result): 16 if root is None: return 17 self.helper(root.left,result) 18 result.append(root.val) 19 self.helper(root.right, result) 20 21# Recursive-2 Another way Anonymous function 22class Solution: 23 def inorderTraversal(self, root: TreeNode) -> List[int]: 24 def helper(root: TreeNode): 25 if not root: return 26 helper(root.left) 27 res.append(root.val) 28 helper(root.right) 29 res = list() 30 helper(root) 31 return res 32 33# Recursive-3 more clean code 34class Solution: 35 def inorderTraversal(self, root: TreeNode) -> List[int]: 36 if not root:return [] 37 res = [] 38 res+=self.preorderTraversal(root.left) 39 res.append(root.val) 40 res+=self.preorderTraversal(root.right) 41 return res
Iterative
1# Definition for a binary tree node. 2# class TreeNode: 3# def __init__(self, val=0, left=None, right=None): 4# self.val = val 5# self.left = left 6# self.right = right 7 8# Solution - 1 9class Solution: 10 def inorderTraversal(self, root: TreeNode) -> List[int]: 11 if not root: return 12 stack, result = [], [] 13 while stack or root: 14 while root: 15 stack.append(root) 16 root = root.left 17 node = stack.pop() 18 result.append(node.val) 19 root = node.right 20 return result 21 22# Solution - 2 简化Solution-1 23class Solution: 24 def inorderTraversal(self, root: TreeNode) -> List[int]: 25 stack, result = [], [] 26 while stack or root: 27 if root: 28 stack.append(root) 29 root = root.left 30 else: 31 node = stack.pop() 32 result.append(node.val) 33 root = node.right 34 return result 35 36# Solution - 3 37class Solution2: 38 def inorderTraversal(self, root: TreeNode) -> List[int]: 39 stack, result = [], [] 40 while stack or root: 41 if root: 42 stack.append(root) 43 root = root.left 44 else: 45 node = stack.pop() 46 result.append(node.val) 47 root = node.right 48 return result
145. 二叉树的后序遍历
Recursive
1# Definition for a binary tree node. 2# class TreeNode: 3# def __init__(self, val=0, left=None, right=None): 4# self.val = val 5# self.left = left 6# self.right = right 7 8# Recursive-1 9class Solution: 10 def postorderTraversal(self, root: TreeNode) -> List[int]: 11 result = [] 12 self.helper(root, result) 13 return result 14 15 def helper(self, root, result): 16 if root is None: return 17 self.helper(root.left,result) 18 self.helper(root.right, result) 19 result.append(root.val) 20 21# Recursive-2 Another way Anonymous function 22class Solution: 23 def postorderTraversal(self, root: TreeNode) -> List[int]: 24 def helper(root: TreeNode): 25 if not root: return 26 helper(root.left) 27 helper(root.right) 28 res.append(root.val) 29 res = list() 30 helper(root) 31 return res 32 33# Recursive-3 more clean code 34class Solution: 35 def postorderTraversal(self, root: TreeNode) -> List[int]: 36 if not root:return [] 37 res = [] 38 res+=self.preorderTraversal(root.left) 39 res+=self.preorderTraversal(root.right) 40 res.append(root.val) 41 return res
Iterative
1# Solution - 1 2class Solution: 3 def postorderTraversal(self, root: TreeNode) -> List[int]: 4 stack, result = [], [] 5 while root or stack: 6 while root: 7 result.append(root.val) 8 stack.append(root) 9 root = root.right 10 node = stack.pop() 11 root = node.left 12 return result[::-1] 13 14 # Solution - 2 15class Solution: 16 def postorderTraversal(self, root: TreeNode) -> List[int]: 17 stack, result = [], [] 18 while stack or root: 19 if root: 20 result.append(root.val) 21 stack.append(root) 22 root = root.right 23 else: 24 node = stack.pop() 25 root = node.left 26 return result[::-1] 27 28# Solution - 3 29class Solution: 30 def postorderTraversal(self, root: TreeNode) -> List[int]: 31 if not root: return 32 stack, result = [root], [] 33 while stack: 34 node = stack.pop() 35 if node: 36 result.append(node.val) 37 stack.append(node.left) 38 stack.append(node.right) 39 return result[::-1]
二叉树迭代遍历模版-Python
1# 前序遍历 2# Solution-1 3class Solution1: 4 def preorderTraversal(self, root: TreeNode) -> List[int]: 5 if not root: return 6 stack, result = [], [] 7 while root or stack: 8 while root: 9 result.append(root.val) 10 stack.append(root) 11 root = root.left 12 tmp = stack.pop() 13 root = tmp.right 14 return result 15 16# 中序遍历 17class Solution: 18 def inorderTraversal(self, root: TreeNode) -> List[int]: 19 if not root: return 20 stack, result = [], [] 21 while stack or root: 22 while root: 23 stack.append(root) 24 root = root.left 25 node = stack.pop() 26 result.append(node.val) 27 root = node.right 28 return result
由递归到迭代，基本的思想就是由递归中由系统维护的栈，转为手动维护。
