二叉树（Binary Tree）

基本概念 #

父节点，子节点，叶子节点 #

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

高度和深度 #

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

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

一些特性 #

在二叉树的第 i 层上至多有 $ 2 ^ { i-1 } $ 个结点（i>=1）
深度为 k 的二叉树最多有 $ 2^{k}-1 $ 个结点（k>=1）。
如果树有 n 个节点，则有 n-1 条边
如果有 a 个叶节点，则有 a-1 个非叶节点
具有 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的结点一一对应时称之为完全二叉树。

二叉搜索树 #

特点：

左子树的所有节点值小于根的节点值（注意不含等号）
右子树的所有节点值大于根的节点值（注意不含等号）
没有键值相等的节点

由此可得：

二叉搜索树的中序遍历结果是一个有序列表，这个性质很有用。
但是二叉搜索树不一定平衡，因此引申出平衡二叉搜索树。

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

平衡二叉树（AVL 树） #

平衡二叉树（Adelson-Velsky and Landis Tree）具有二叉搜索树的性质，同时又多了以下特性：

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

左旋 #

右旋 #

题目 #

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;
};