1、树结构
树是一种抽象数据类型（ADT）或是实现这种抽象数据类型的数据结构，用来模拟具有树状结构性质的数据集合。它是由 n(n>0)个有限节点组成一个具有层次关系的集合。
（1）树的遍历，递归法，深度优先
前序遍历首先访问根节点，然后遍历左子树，最后遍历右子树。
中序遍历是先遍历左子树，然后访问根节点，然后遍历右子树。
后序遍历是先遍历左子树，然后遍历右子树，最后访问树的根节点。
递归实现：
三个规则：
（1）递归终止条件
（2）确定单层逻辑
（3）确定递归函数的参数和返回值：
确定哪些参数是递归的过程中需要处理的，那么就在递归函数里加上这个参数， 并且还要明确每次递归的返回值是什么进而确定递归函数的返回类型。
def preorderTraversal(self, root: TreeNode) -> List[int]:
def preorder(root: TreeNode):
if not root:
return
result.append(root.val)
preorder(root.left)
preorder(root.right)
result=list()
preorder(root)
return result
def inorderTraversal(self, root: TreeNode) -> List[int]:
def inorder(root: TreeNode):
if not root:
return
inorder(root.left)
res.append(root.val)
inorder(root.right)
res=list()
inorder(root)
return res
def postorderTraversal(self, root: TreeNode) -> List[int]:
def postorder(root: TreeNode):
if not root:
return
postorder(root.left)
postorder(root.right)
res.append(root.val)
res=[]
postorder(root)
return res
（2）层序遍历，迭代法，广度优先
层序遍历就是逐层遍历树结构。
广度优先搜索是一种广泛运用在树或图这类数据结构中，遍历或搜索的算法。 该算法从一个根节点开始，首先访问节点本身。 然后遍历它的相邻节点，其次遍历它的二级邻节点、三级邻节点，以此类推。
当我们在树中进行广度优先搜索时，我们访问的节点的顺序是按照层序遍历顺序的。
1）每层节点分层
关键是：计算每一层节点个数确定迭代次数
def levelOrder(self, root: TreeNode) -> List[List[int]]:
if not root:
return []
node=[]
res=[]
node.append(root)
while node:
k=len(node)
res1=[]
for i in range(k):
l=node.pop(0)
res1.append(l.val)
if l.left:
node.append(l.left)
#res.append(root.left.val)
if l.right:
node.append(l.right)
#res.append(root.right.val)
res.append(res1)
return res
2）每层节点不分层
def levelOrder(self, root: TreeNode) -> List[List[int]]:
if not root:
return []
node=[]
res=[]
node.append(root)
while node:
l=node.pop(0)
res.append(l.val)
if l.left:
node.append(l.left)
#res.append(root.left.val)
if l.right:
node.append(l.right)
#res.append(root.right.val)
return res
参考资料：
1、树 https://leetcode-cn.com/tag/tree/
2、彻底吃透前中后序递归法（递归三部曲）和迭代法（不统一写法与统一写法）
https://leetcode-cn.com/problems/binary-tree-preorder-traversal/solution/dai-ma-sui-xiang-lu-chi-tou-qian-zhong-hou-xu-de-d/
网友评论