树的遍历
前序遍历（Preorder Traversal）
先访问根节点，然后访问左子树，最后访问右子树。在访问左、右子树的时候，同样，先访问子树的根节点，再访问子树根节点的左子树和右子树，这是一个不断递归的过程。
中序遍历（Inorder Traversal）
方法：先访问左子树，然后访问根节点，最后访问右子树，在访问左、右子树的时候，同样，先访问子树的左边，再访问子树的根节点，最后再访问子树的右边。
应用场景：最常见的是二叉搜索树，由于二叉搜索树的性质就是左孩子小于根节点，根节点小于右孩子，对二叉搜索树进行中序遍历的时候，被访问到的节点大小是按顺序进行的。
后序遍历（Postorder Traversal）
方法：先访问左子树，然后访问右子树，最后访问根节点。
应用场景：在对某个节点进行分析的时候，需要来自左子树和右子树的信息。收集信息的操作是从树的底部不断地往上进行，好比你在修剪一棵树的叶子，修剪的方法是从外面不断地往根部将叶子一片片地修剪掉。
代码
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
#前序遍历
def preorderTraversal(self, root: TreeNode) -> List[int]:
if root:
return [root.val] + self.preorderTraversal(root.left) + self.preorderTraversal(root.right)
else:
return []
#中序遍历
def inorderTraversal(self, root: TreeNode) -> List[int]:
if root:
return self.inorderTraversal(root.left) + [root.val] + self.inorderTraversal(root.right)
else:
return []
#后序遍历
def postorderTraversal(self, root: TreeNode) -> List[int]:
if root:
return self.postorderTraversal(root.left) + self.postorderTraversal(root.right) + [root.val]
else:
return []
二叉搜索树
二叉搜索树的性质：对于每个节点来说，该节点的值比左孩子大，比右孩子小，而且一般来说，二叉搜索树里不出现重复的值。
二叉搜索树中序遍历即可得到升序数组。
