一、概念
树（Tree）是一种具有抽象数据类型的数据结构。用此来模拟具有树状结构性质的数据集合。之所以叫做树结构，是因为我们它形似一种倒挂的树。
相关的术语如下面的思维导图：
树的相关术语
树的种类
二、二叉树
从前面的定义可以知道，二叉树的每个节点最多有两个子树的树结构。通常子树被称为左子树和右子树。
在二叉树的遍历的遍历当中，要么是横向的遍历，要么就是纵向的遍历。
1、广度遍历
例子： 0 1 2 3 4 5 6 7 8 9
2、深度遍历
- 先序遍历：
先是访问根节点，然后递归使用先序遍历访问左子树，然后再递归使用先序遍历访问右子树。
根节点->左子树->右子树
例子：0 1 3 7 8 4 9 2 5 6 - 中序遍历
左子树->根节点->右子树
例子：7 3 8 1 9 4 0 5 2 6 - 后序遍历
左子树->右子树->根节点
例子：7 8 3 9 4 1 5 6 2 0
二叉树的代码实现：
class TreeNode(object):
"""二叉树节点的定义"""
def __init__(self, item):
self.val = item
self.left = None
self.right = None
class Tree(object):
"""二叉树定义"""
def __init__(self):
self.root = None
def add(self, item):
node = TreeNode(item)
if not self.root:
self.root = node
return
queue = [self.root]
while queue:
cur_node = queue.pop(0)
if not cur_node.left:
cur_node.left = node
return
else:
queue.append(cur_node.left)
if not cur_node.right:
cur_node.right = node
return
else:
queue.append(cur_node.right)
def breadthTravel(self):
"""广度遍历"""
if not self.root: #根节点为空就返回
return
queue = [self.root]
while queue:
cur_node = queue.pop(0)
print(cur_node.val, end=" ")
if cur_node.left:
queue.append(cur_node.left)
if cur_node.right:
queue.append(cur_node.right)
def preorderTraversal(self, node):
"""先序遍历"""
if not node: #根节点为空就返回
return
print(node.val, end=" ")
self.preorderTraversal(node.left)
self.preorderTraversal(node.right)
def inorderTraversal(self, node):
"""中序遍历"""
if not node: #根节点为空就返回
return
self.inorderTraversal(node.left)
print(node.val, end=" ")
self.inorderTraversal(node.right)
def postorderTraversal(self, node):
"""后序遍历"""
if not node: #根节点为空就返回
return
self.postorderTraversal(node.left)
self.postorderTraversal(node.right)
print(node.val, end=" ")
if __name__ == "__main__":
tree = Tree()
tree.add(0)
tree.add(1)
tree.add(2)
tree.add(3)
tree.add(4)
tree.add(5)
tree.add(6)
tree.add(7)
tree.add(8)
tree.add(9)
tree.breadthTravel() # 0 1 2 3 4 5 6 7 8 9
tree.preorderTraversal(tree.root) # 0 1 3 7 8 4 9 2 5 6
tree.inorderTraversal(tree.root) # 7 3 8 1 9 4 0 5 2 6
tree.postorderTraversal(tree.root) # 7 8 3 9 4 1 5 6 2 0
三、LeetCode题目
典型题目：
LeetCode里面也有题目考察了二叉树的前、中、后序遍历，题目分别是144、94、145。都是要求了采用迭代的方式去完成题目，下面将递归和迭代的方式都总结到下面了。
- 二叉树的前序遍历
- 二叉树的中序遍历
- 二叉树的后序遍历
- leetcode 226、翻转一颗二叉树
思路：采用递归的思想来进行求解
1、确定递归终止的条件，也就是我们传入的root节点为空的时候，我们就return。
2、确定我们的递归过程，先是递归的去调用我们左子树，然后是递归的调用我们的右子树，然后就是对左子树和右子树进行一个交换，再return 回来我们已经翻转完成了的二叉树。这样的话，我们就完成这个操作了。
class Solution:
def invertTree(self, root):
"""
:type root: TreeNode
:rtype: TreeNode
"""
if root is None:
return
self.invertTree(root.left)
self.invertTree(root.right)
root.left , root.right = root.right, root.left
return root
- LeetCode 104. 二叉树的最大深度
思路：通过递归来完成
1、确定我们的递归终止条件，当我们传入的root节点是空的时候，那么深度就是0了。
2、确定我们的递归过程，先是对我们的左子树进行递归调用maxDepth函数，然后是对我们右子树进行递归调用maxDepth函数，最后返回的就是这两个深度的最大值+1.
class Solution:
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 max(left_depth, right_depth)+1
- LeetCode 111.二叉树的最小深度
思路：采用递归思想来求解
这个题目和上面的那道题有点类似，但是递归终止的条件却是不同的。
1、递归终止条件：当root节点的左子树或者右子树为空的时候，我们就是return ldepth + rdepth+1，否则我们就return 一下min(ldepth,rdepth)+1，在这之前还是需要哦按段一下root是不是空的，是空的话，那么就return 0了
2、递归过程：分别对root的左子树和右子树进行递归的条用minDepth。
class Solution:
def minDepth(self, root):
"""
:type root: TreeNode
:rtype: int
"""
if not root:
return 0
ldepth = self.minDepth(root.left)
rdepth = self.minDepth(root.right)
if root.left == None or root.right==None:
return ldepth + rdepth+1
else:
return min(ldepth,rdepth)+1
LeetCode 589. N叉树的前序遍历
思路一：采用递归的方式进行完成
递归过程：遍历root节点的所有孩子节点，进行一个递归的调用preorder函数
class Solution:
def preorder(self, root: 'Node') -> List[int]:
if not root:
return []
ret = [root.val]
if root.children:
for node in root.children:
ret.extend(self.preorder(node))
return ret
持续更新中...
数据结构与算法系列博客：
一、数据结构与算法概述
二、数组及LeetCode典型题目分析
三、链表（Linked list）以及LeetCode题
四、栈与队列（Stack and Queue
五、树（Trees）
六、递归与回溯算法
七、动态规划
八、排序与搜索
九、哈希表
参考资料：
网友评论