# 👉 二叉树基础

二叉树(Binary Tree)是一种树形结构，一棵二叉树通常由根节点，分支节点，叶子节点组成。它的特点是每个节点最多只有两个分支节点，而每个分支节点也常常被称作为一棵子树。

它可以没有根结点，作为一棵空树存在；
如果它不是空树，那么必须由根结点、左子树和右子树组成，且左右子树都是二叉树。

# 二叉树的先、中、后序遍历

# 二叉树的先、中、后序遍历的递归实现

// 先序遍历
function preoder(root) {
    if (!root) return false;

    console.log(`当前遍历节点为: ${root.val}`);
    preorder(root.left);
    preorder(root.right);
}

// 中序遍历
function inoder(root) {
    if (!root) return false;

    preorder(root.left);
    console.log(`当前遍历节点为: ${root.val}`);
    preorder(root.right);
}

// 后序遍历
function postorder(root) {
    if (!root) return false;

    preorder(root.left);
    console.log(`当前遍历节点为: ${root.val}`);
    preorder(root.right);
}

# 二叉树的先、中、后序遍历的迭代法实现

上面已经通过递归法实现了二叉树的先、中、后序遍历，而递归和栈往往有着脱不开的干系，因此能用递归法实现的题，需转换一种方法实现，这个时候可往栈方向思考，使用栈来模拟递归的过程

来自修言大大的小册：大家谨记，二叉树题目的输出一般为真数组（往往是节点值？），而输入只要没有额外强调，那么一般来说它都是基于这样的一个对象结构嵌套而来的：

function TreeNode(val) {
    this.val = val;
    this.left = this.right = null;
}

const root = {
    val: "A",
    left: {
        val: "B",
        left: {
            val: "D",
        },
        right: {
            val: "E",
        },
    },
    right: {
        val: "C",
        right: {
            val: "F",
        },
    },
};

// 对应为：[A,B,C,D、E、null、F]

这类题的根本思路，就是通过合理地安排入栈和出栈的时机、使栈的出栈序列符合二叉树的先、中、后序遍历规则。

先序遍历顺序：根->左->右（这就成了我们后面需要达成的一个期望出栈顺序）

需要注意的是，我们遍历的起点就是根结点，因此出入栈的顺序：
1）取根节点，入栈
2）取此根节点，pop 出栈，push 结果数组
3）若有右子节点，取右子节点，入栈
4）若有左子节点，取左子节点，入栈

本质上是将当前子树的根结点入栈、出栈，随后再将其对应左右子树入栈、出栈的过程。

后序遍历顺序：左->右->根

后序遍历和先序遍历有点类似，都是先对根节点处理，然后再对孩子节点处理。

中序遍历顺序：左->根->右

中序遍历的迭代和前面两种有点不太一样。前两者的出栈、入栈逻辑差别不大——都是先处理根结点，然后处理孩子结点。而中序遍历中，根结点不再出现在遍历序列的边界、而是出现在遍历序列的中间。

中序遍历的序列规则是左 -> 中 -> 右，这意味着我们必须首先定位到最左的叶子结点。然后途径过的每一个结点，我们都要及时地把它入栈。这样当最左的叶子结点出栈时，第一个回溯到的就是它的父结点。

// 先序遍历
function preorder(root) {
    const result = [];
    if (!root) return result;

    const stack = [];
    stack.push(root);

    while (stack.length) {
        let cur = stack.pop();
        result.push(cur.val);

        if (cur.right) {
            stack.push(cur.right);
        }

        if (cur.left) {
            stack.push(cur.left);
        }
    }

    return result;
}

// 后序遍历
function postorder(root) {
    const result = [];
    if (!root) return result;

    const stack = [root];

    while (stack.length) {
        let cur = stack.pop();
        result.unshift(cur.val);

        cur.left && stack.push(cur.left);
        cur.right && stack.push(cur.right);
    }

    return result;
}

// 中序遍历
function inorder(root) {
    const result = [];

    if (!root) return result;

    const stack = [];
    let cur = root;

    while (cur || stack.length) {
        // 一直定位到最左叶子结点，并将途径的结点入栈
        while (cur) {
            stack.push(cur);
            cur = cur.left;
        }

        cur = stack.pop();

        result.push(cur.val);

        // 如果存在右节点，获取右节点，并对右结点进行同样操作
        cur = cur.right;
    }

    return result;
}

# 二叉树的层次遍历

关于层序遍历，看到层序遍历就应该条件反射出BFS+队列。

102. 二叉树的层序遍历 (opens new window)

function levelOrder(root) {
    const result = [];
    if (!root) return result;

    const queue = [];
    queue.push(root);

    while (queue.length) {
        // 获取当前层级树（第level层）
        const level = queue.length;
        const item = [];

        // 获取当前层级的元素进行操作
        for (let i = 0; i < level; i++) {
            let cur = queue.shift();
            item.push(cur.val);

            // 获取自己下一层的左右子节点，推入队列
            cur.left && queue.push(cur.left);
            cur.right && queue.push(cur.right);
        }
        result.push(item);
    }

    return result;
}

# 二叉搜索树 BST

二叉搜索树（Binary Search Tree）简称 BST，是二叉树的一种特殊形式。它有很多别名，比如排序二叉树、二叉查找树等等。

二叉搜索树中，递归的定义：
1）是一棵空树
2）是一棵由根结点、左子树、右子树组成的树，同时左子树和右子树都是二叉搜索树，且左子树上所有结点的数据域都小于等于根结点的数据域，右子树上所有结点的数据域都大于等于根结点的数据域。

这里的数据域的有序性指：二叉搜索树上的每一棵子树，都应该满足左孩子 <= 根结点 <= 右孩子这样的大小关系。

满足以上两个条件之一的二叉树，就是二叉搜索树。

# 二叉树搜索树高频操作

查找数据域为某一特定值的结点

function searchBST(root, n) {
  if(!root) return;

  // 找到目标对象，输出
  if(root.val === n) {
    console.log('目标结点是：', root)
  } else if(root.val > n) {
    // 当前值大于目标值，往左节点找
    searchBST(root.left, n);
  } else if(root.val < n) {
    // 当前值小于目标值，往右节点找
    searchBST(root.right, n);
  }

插入新结点

function insertBST(root, n) {
  if(!root) {
    // 直到为空，建一个节点插入至对应位置
    root = new TreeNode(root);
    return root;
  }

  if(root.val > n) {
    // 当前值大于目标值，往左节点找
    root.left = insertBST(root.left, n);
  } else {
    // 当前值小于目标值，往右节点找
    root.right = insertBST(root.right, n);
  }

删除指定结点

function deleteNode(root, key) {
    if (!root) return root;

    if (root.val > key) {
        // 往左子树遍历查找
        root.left = deleteNode(root.left, key);
    } else if (root.val < key) {
        // 往右子树遍历查找
        root.right = deleteNode(root.right, key);
    } else {
        // 找到了进行删除，情况有以下几种：
        if (!root.left && !root.right) {
            // 不存在孩子，则直接删除
            root = null;
        } else if (!root.left && root.right) {
            // 只存在右孩子
            root = root.right;
        } else if (root.left && !root.right) {
            // 只存在左孩子
            root = root.left;
        } else {
            // 左右孩子都存在
            // 两种解决方案：找到右节点的最小节点/找到左节点的最大节点作为替换
            // 前驱即左孩子的最右节点，后继则右孩子的最左节点
            const temp = findLeftMax(root.left);

            // 从root.left开始遍历，将符合条件的节点在原位置中删除
            root.val = temp.val;
            root.left = deleteNode(root.left, temp.val);
        }
    }

    return root;
}

// 寻找二叉搜索树左子树最大值
function findLeftMax(root) {
    while (root.right) {
        root = root.right;
    }
    return root;
}

// 右孩子树的最小值
function findRightMin(root) {
    while (root.left) {
        root = root.left;
    }
    return root;
}

判断是否是合法的 BST

利用二叉搜索树的特性进行判别：左节点数据域 < 根节点数据域 < 右节点数据域

var isValidBST = function(root) {
    const dfs = function(root, min, max) {
        if (!root) return true;
        if (root.val >= max || root.val <= min) {
            return false;
        }
        return dfs(root.left, min, root.val) && dfs(root.right, root.val, max);
    };

    return dfs(root, -Infinity, Infinity);
};

# 二叉搜索树特性

二叉搜索树的中序遍历序列是有序的！

# 平衡二叉树 AVL Tree

平衡二叉树的特性：一个高度平衡二叉树是指一个任意结点的左右子树的高度差的绝对值不超过 1的二叉树。

对于一个输入的树形数组：
当数组长度为奇数时，以中间元素为根结点，可把数组“提”成二叉树，那么根结点左右两侧的元素个数是一样的，所以站在根结点来看，左右子树的高度差为 0。
当数组长度为偶数时，选择中间靠左的元素为界或选择中间靠右的元素为界，两侧元素个数差值的绝对值都是 1。

二叉搜索树的妙处就在于它把“二分”这种思想以数据结构的形式表达了出来。
在一个构造合理的二叉搜索树里，我们可通过对比当前结点和目标值之间的大小关系，缩小下一步的搜索范围（比如只搜索左子树或者只搜索右子树），进而规避掉不必要的查找步骤，降低搜索过程的时间复杂度。

平衡二叉树由于利用了二分思想，查找操作的时间复杂度仅为 O(logN)

# 对操作的考察

以平衡二叉树的构造为例
1382. 将二叉搜索树变平衡 (opens new window)

给你一棵二叉搜索树，请你返回一棵平衡后的二叉搜索树，新生成的树应该与原来的树有着相同的节点值。

思路：对于有序的数组，仅需将数组中间值“提起”，即可构建一颗高度平衡二叉树。此题给的是一颗二叉搜索树。而二叉搜索树的中序遍历是一个有序的数组，利用这个特性即可将二叉搜索树生成一个有序的数组，进而转为一个平衡二叉树

var balanceBST = function(root) {
    let nums = [];
    const buildInorder = function(root) {
        if (!root) return;
        buildInorder(root.left);
        nums.push(root.val);
        buildInorder(root.right);
    };

    buildInorder(root);

    const buildAVL = function(min, max) {
        if (min > max) return null;
        const mid = Math.floor((min + max) / 2);
        const root = new TreeNode(nums[mid]);
        root.left = buildAVL(min, mid - 1);
        root.right = buildAVL(mid + 1, max);
        return root;
    };

    return buildAVL(0, nums.length - 1);
};

# 对特性的考察

对平衡二叉树的判定

剑指 Offer 55 - II. 平衡二叉树 (opens new window)

题目描述：给定一个二叉树，判断它是否是高度平衡的二叉树。

这里再次重复一次平衡二叉树的特性：任何结点的左右子树高度差绝对值不超过 1。

任何结点表明每个结点都需要进行这样子的一个校验，即需重复进行（重复联想到递归）；
而左右子树高度差绝对值不超过 1则表明需递归式。

var isBalanced = function(root) {
    const dfs = function(root) {
        if (!root) return 0;

        let left = dfs(root.left);
        let right = dfs(root.right);

        // 根结点的左右子树高度超过1，返回-1
        if (left === -1 || right === -1 || Math.abs(left - right) > 1) {
            return -1;
        }

        return Math.max(left, right) + 1;
    };

    return dfs(root) !== -1;
};

👉 二叉树应用 →