本章主要探讨二叉树相关内容，主要原因是因为二叉树和递归思想息息相关。而且二叉树作为数据结构的入门的必备知识，
所以其重要性不言而喻。
在讲解二叉树之前，先说说数据结构的两大特点： 存储和访问。 数据结构的设计也常常涉及这两个方面。一般来说存储简单，访问花销就会大。反之也成立。
存储自不必多说，无非就是数据插入的方式不同。具体由数据结构特性决定。
但是访问不同，其涉及到算法思路。不同的思路访问方式千差万别，但是离不开两大访问方式、
- 迭代遍历: 学习编程的时候常常使用的就是这种方式，不多讨论。
- 递归遍历： 通过函数自身的反复调用，本章核心讨论点。
常用的数据结构 数组和链表均能使用上面的两种方式进行遍历
下面就详细讨论二叉树中递归的使用思想， 从而打开数据结构算法的大门。
二叉树的遍历
二叉树可看做二叉链表， 一般使用递归遍历较方便。遍历的方式由根节点的访问区分。
- 前序遍历： 根节点优先访问
- 中序遍历： 根节点其次访问
- 后续遍历： 根节点最后访问
class Solution(object):
def preorderTraversal(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
self.res = []
self.traversal(root)
return self.res
def traversal(self, root):
if not root: return
根节点访问
self.res.append(root.val)
self.traversal(root.left)
self.traversal(root.right)
改变根节点访问代码的位置，就可以变换成其他两种方式。
通过遍历能够解决的问题
- 二叉树的最大深度
class Solution(object):
def maxDepth(self, root):
"""
:type root: TreeNode
:rtype: int
"""
if not root: return 0
left_depth = self.maxDepth(root.left)
right_depth = self.maxDepth(root.right)
return 1 + max(left_depth, right_depth)
二叉树的直径
二叉树的翻转
class Solution(object):
def invertTree(self, root):
"""
:type root: TreeNode
:rtype: TreeNode
"""
self.traversal(root)
return root
def traversal(self, root):
if not root: return
tmp = root.left
root.left = root.right
root.right = tmp
self.traversal(root.left)
self.traversal(root.right)
class Solution(object):
def invertTree(self, root):
"""
:type root: TreeNode
:rtype: TreeNode
"""
left = self.invertTree(root.left)
right = self.invertTree(root.right)
root.left = right
root.right = left
return root
- 二叉树展开为链表
class Solution(object):
def flatten(self, root):
"""
:type root: TreeNode
:rtype: None Do not return anything, modify root in-place instead.
"""
self.res = []
self.tarversal(root)
return self.res
def tarversal(self, root):
self.res = []
if not root: return
self.res.append(root.val)
while root.left:
self.tarversal(root.left)
while root.right:
self.tarversal(root.right)
二叉树的构造
- 二叉树 = 根节点+ 左子树 + 右子树
- 递归使得左右子树循环到最小单位
- 二叉树的结构体
class TreeNode(object):
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
- 最大二叉树
class solution(object):
def construct_maxTree(self, nums:list) -> TreeNode:
if not nums: return
max_val = max(nums)
max_index = nums.index(max_val)
root = TreeNode(max_val)
root.left = self.construct_maxTree(nums[0: max_index])
root.right = self.construct_maxTree(nums[max_index+1:])
return root
def preorderTraversal(self, root):
self.res = []
self.traversal(root)
return self.res
def traversal(self, root):
if not root: return
self.res.append(root.val)
self.traversal(root.left)
self.traversal(root.right)
- 根据前序和中序遍历结果构造二叉树
class Solution1(object):
def build_tree(self, pre_order, in_order) -> TreeNode:
return self.build(pre_order, 0, len(pre_order)-1, in_order, 0, len(in_order)-1)
def build(self, pre_order, pre_start,pre_end,in_order,in_start,in_end):
if pre_start > pre_end: return
root_val = pre_order[pre_start]
index_val = in_order.index(root_val)
left_size = index_val - in_start
root = TreeNode(root_val)
root.left = self.build(pre_order,pre_start+1, pre_start+left_size, in_order, in_start, index_val-1)
root.right = self.build(pre_order, pre_start+left_size+1, pre_end,in_order, index_val+1, in_end)
return root
def preorderTraversal(self, root):
self.res = []
self.traversal(root)
return self.res
def traversal(self, root):
if not root: return
self.traversal(root.left)
self.traversal(root.right)
self.res.append(root.val)
- 根据中序和后序遍历结果构造二叉树
class Solution2(object):
def build_tree(self, in_order, post_order) -> TreeNode:
return self.build(in_order, 0, len(in_order)-1, post_order, 0, len(post_order)-1)
def build(self, in_order,in_start, in_end, post_order, post_start, post_end):
if post_start > post_end: return
root_val = post_order[post_end]
index_val = in_order.index(root_val)
left_size = index_val - in_start
root = TreeNode(root_val)
root.left = self.build(in_order, in_start, index_val-1, post_order, post_start, post_start+left_size-1)
root.right = self.build(in_order, index_val+1, in_end, post_order, post_start+left_size , post_end -1)
return root
def preorderTraversal(self, root):
self.res = []
self.traversal(root)
return self.res
def traversal(self, root):
if not root: return
self.res.append(root.val)
self.traversal(root.left)
self.traversal(root.right)
- 根据前序和后序遍历结果构造二叉树
class Solution(object):
def build_tree(self, pre_order, post_order) -> TreeNode:
# self.val_index = dict(zip(post_order, range(len(post_order))))
return self.build(pre_order, 0, len(pre_order)-1, post_order, 0, len(post_order)-1)
def build(self, pre_order,pre_start, pre_end, post_order, post_start, post_end):
if pre_start > pre_end: return
if pre_start == pre_end: return TreeNode(pre_order[pre_start])
root_val = pre_order[pre_start]
left_root_val = pre_order[pre_start + 1]
index_val = post_order.index(left_root_val)
# index_val = self.val_index[left_root_val]
left_size = index_val - post_start + 1
root = TreeNode(root_val)
root.left = self.build(pre_order, pre_start+1, pre_start+left_size, post_order, post_start, index_val)
root.right = self.build(pre_order, pre_start+left_size+1, pre_end, post_order, index_val+1, post_end-1)
return root
def preorderTraversal(self, root):
self.res = []
self.traversal(root)
return self.res
def traversal(self, root):
if not root: return
self.res.append(root.val)
self.traversal(root.left)
self.traversal(root.right)
递归思想可以在二叉树的使用中充分体现，而且递归思想作为访问的一大方式也显得极其重要。掌握递归也是后续掌握其他算法思想的一大助力。
