算法(2)--二叉树

二叉树

二叉树（Binary Tree）是一种常用的数据结构，在计算机科学中有广泛的应用。它是一种非线性数据结构，每个节点最多有两个子节点，通常这两个子节点被称为左子节点（left child）和右子节点（right child）。

有一些特别的二叉树，满二叉树就是每一层节点都是满的，除了叶子节点外，每个节点都有两个子节点。假设深度为 h，那么总节点数就是$2^h - 1$。 完全二叉树是指，二叉树的每一层的节点都紧凑靠左排列，且除了最后一层，其他每层都必须是满的，完全二叉树的特点：由于它的节点紧凑排列，如果从左到右从上到下对它的每个节点编号，那么父子节点的索引存在明显的规律。平衡二叉树中任何两个叶子节点的高度差不大于 1，二叉搜索树（Binary Search Tree，简称 BST）是一种很常见的二叉树，它的定义是：对于树中的每个节点，其左子树的每个节点的值都要小于这个节点的值，右子树的每个节点的值都要大于这个节点的值。

二叉树的递归/层序遍历

递归遍历

二叉树的递归遍历是一种常用的遍历方式，它利用递归来访问树中的所有节点。二叉树的递归遍历主要有三种方式：前序遍历（Preorder）、中序遍历（Inorder）和后序遍历（Postorder）。前序遍历的顺序是：先访问根节点，然后递归地遍历左子树，最后递归地遍历右子树。中序遍历的顺序是：递归地遍历左子树，然后访问根节点，最后递归地遍历右子树。后序遍历的顺序是：递归地遍历左子树，然后递归地遍历右子树，最后访问根节点。

class TreeNode:
    def __init__(self, value=0, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

def preorder_traversal(root):
    if root is None:
        return []
    result = []
    _preorder_helper(root, result)
    return result

def _preorder_helper(node, result):
    if node:
        result.append(node.value)  # 访问节点
        _preorder_helper(node.left, result)  # 遍历左子树
        _preorder_helper(node.right, result)  # 遍历右子树

层序遍历

二叉树的层序遍历，顾名思义，就是一层一层地遍历二叉树。这个遍历方式需要借助队列来实现。

参考文献

https://labuladong.online/algo/data-structure-basic/binary-tree-basic/#%E5%87%A0%E7%A7%8D%E5%B8%B8%E8%A7%81%E7%9A%84%E4%BA%8C%E5%8F%89%E6%A0%91