二叉树(Binary Tree)

基本概念 #

父节点,子节点,叶子节点 #

叶子节点: 一棵树当中没有子结点的结点称为叶子结点。

高度和深度 #

  • 树的高度:节点到叶子节点的最大值就是其高度。
  • 树的深度:高度和深度是相反的,高度是从下往上数,深度是从上往下。

注意: 一般默认是把根节点的深度设为 1,把子节点的高度设为 1,比如 104. 二叉树的最大深度。在面试的时候最好要确认一下。

一些特性 #

  1. 在二叉树的第 i 层上至多有 $ 2 ^ { i-1 } $ 个结点(i>=1)
  2. 深度为 k 的二叉树最多有 $ 2^{k}-1 $ 个结点(k>=1)。
  3. 如果树有 n 个节点,则有 n-1 条边
  4. 如果有 a 个叶节点,则有 a-1 个非叶节点
  5. 具有 n 个节点的树最小深度为 log2 n + 1

JavaScript #

function TreeNode(val, left, right) {
     this.val = (val===undefined ? 0 : val)
     this.left = (left===undefined ? null : left)
     this.right = (right===undefined ? null : right)
}

Golang #

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

数据结构 #

满二叉树 #

对于满二叉树,除最后一层无任何子节点外,每一层上的所有结点都有两个子结点二叉树。

完全二叉树 #

定义1:若设二叉树的深度为h,除第 h 层外,其它各层 (1~h-1) 的结点数都达到最大个数,第 h 层所有的结点都连续集中在最左边,这就是完全二叉树。

定义2:对于深度为K的,有n个结点的二叉树,当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。

二叉搜索树 #

特点:

  1. 左子树的所有节点值小于根的节点值(注意不含等号)
  2. 右子树的所有节点值大于根的节点值(注意不含等号)
  3. 没有键值相等的节点

由此可得:

  1. 二叉搜索树的中序遍历结果是一个有序列表,这个性质很有用。

  2. 但是二叉搜索树不一定平衡,因此引申出平衡二叉搜索树。

平衡二叉查找树可以修复二叉查找树形状不规则的问题。

平衡二叉树(AVL 树) #

平衡二叉树(Adelson-Velsky and Landis Tree)具有二叉搜索树的性质,同时又多了以下特性:

  1. 除了空树,任何一个结点的左子树与右子树都是平衡二叉树,并且高度之差的绝对值不超过 1。
  2. 平衡二叉树在插入新的子节点时,可能会形成最小失衡子树
  3. 平衡二叉树的失衡调整主要是通过旋转最小失衡子树来实现的。根据旋转的方向有两种处理方式,左旋右旋

左旋 #

右旋 #

题目 #

110. 平衡二叉树

二叉树遍历 #

广度优先搜索(BFS) #

也叫层序遍历。

102. 二叉树的层序遍历

深度优先搜索(DFS) #

先、中、后指的是根节点的先后。

遍历 #

递归方式按照这个模板推导即可。

void traverse(TreeNode root) {
    if (root == null) {
        return;
    }
    // 前序位置
    traverse(root.left);
    // 中序位置
    traverse(root.right);
    // 后序位置
}

先序遍历 #

144. 二叉树的前序遍历

非递归实现

var preorderTraversal = function(root) {
    let stack = []
    let ret = []

    while (root || stack.length) {
        while (root) {
            ret.push(root.val)
            stack.push(root)
            root = root.left
        }
        root = stack.pop()
        root = root.right

    }
    return ret
};

中序遍历 #

94. 二叉树的中序遍历

非递归实现

var inorderTraversal = function(root) {
    const res = [];
    const stk = [];
    while (root || stk.length) {
        while (root) {
            stk.push(root);
            root = root.left;
        }
        root = stk.pop();
        res.push(root.val);
        root = root.right;
    }
    return res;
};

后序遍历 #

145. 二叉树的后序遍历

反向构建 #

105. 从前序与中序遍历序列构造二叉树

106. 从中序与后序遍历序列构造二叉树

889. 根据前序和后序遍历构造二叉树

常见题型 #

589. N 叉树的前序遍历(熟悉 N 叉树)

662. 二叉树最大宽度 (请分别使用 BFS 和 DFS 解决,空间复杂度尽可能低)

834. 树中距离之和

967. 连续差相同的数字 (隐形树的遍历)

1145. 二叉树着色游戏(树上进行决策)

其他树 #

B 树 #

B树和平衡二叉树稍有不同的是B树属于多叉树又名平衡多路查找树(查找路径不只两个)

B+树 #

B*树 #

红黑树 #

R 树 #

参考 #

https://zhuanlan.zhihu.com/p/56066942

https://zhuanlan.zhihu.com/p/27700617

几乎刷完了力扣所有的树题,我发现了这些东西