算法题刷题笔记-二叉树

1. 二叉树基础：

  1. 一些概念：
  • 满二叉树：深度为k的满二叉树必须满足节点总数为$2^k-1$，且第i层的节点数达到最大值$2^{i-1}$
  • 完全二叉树：所有非最后一层节点均有两个子节点，且最后一层节点连续集中在左侧。（从上到下，从左到右，结点编号连续）
  • 二叉搜索树：左子树的所有节点都小于中间节点，右子树的所有节点都大于中间节点。（搜索一个节点的时间复杂度是logn）
  • 平衡二叉搜索树：左子树和右子树的高度差的绝对值不大于1。（map、set、multimap和multiset的底层数据结构都是平衡二叉搜索树，它们插入或检索一个元素的时间复杂度都是logn；unordered_map和unordered_set底层是哈希表）
  1. 储存方式：
  • 链式存储：二叉链表，每个节点类一般有三个对象（left，val和right），分别对应的是该节点的左孩子节点、节点值和右孩子节点。
    1
    2
    3
    4
    5
    class TreeNode:
        def __init__(self, val=0, left=None, right=None):
            self.val = val
            self.left = left
            self.right = right
  • 线性存储：数组，元素i的左孩子节点下标是2i+1，右孩子节点下标是2i+2
  1. 遍历方式：
  • DFS和BFS：前中后序遍历是DFS，层序遍历是BFS；方法可以是队列递归或队列迭代
  • 前中后序主要是看根节点访问的先后次序：前序是中左右，中序是左中右，后序是左右中

2. 二叉树的中序遍历（LC94）