综合文章

# 重建二叉树📕

这是《剑指offer》上一道比较经典的题, 相信你要是看懂了上面二叉树的基本用法, 那么解题就不会那么困难了. 在解每道题的时候, 你可以多想想每种遍历的特性.

# 题目描述

输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。

# 解题思路

  1. 前序遍历的第一项一定是二叉树的根节点;
  2. 二叉树的根节点一定在中序遍历左子树和右子树的中间(包括没有左或右子树的情况): [左子树][根节点][右子树];
  3. 用前序遍历的第一项(也就是根节点)查找到它在中序遍历的第几项,左边的就是左子树,右边为右子树;
  4. 根据左右子树的长度，再次划分两个序列，进一步递归.

img7

# coding

// 定义一个二叉树的节点类
class Node {
    constructor(value, left = null, right = null) {
        this.value = value;
        this.left = left;
        this.right = right;
    }
}
/*
* 根据前序遍历和中序遍历重构二叉树
* @param {Array} preorder
* @param {Array} inorder
* @return {Node} 重构后的树
*/
function reConstruct(preOrder, inOrder) {
    if (!preOrder.length || !inOrder.length) {
        return null
    }
    let root = preOrder[0] // 根节点的值为先序遍历的第一项
    let node = new Node(root) // 新建一个节点

    let i = inOrder.indexOf(root) // 查找到根节点在中序遍历中的位置

    node.left = reConstruct(preOrder.slice(1, i + 1), inOrder.slice(0, i))
    node.right = reConstruct(preOrder.slice(i + 1), inOrder.slice(i + 1))

    return node
}

const preArray = [1, 2, 4, 7, 3, 5, 6, 8];
const midArray = [4, 7, 2, 1, 5, 3, 8, 6];
const binTree = reConstruct(preArray, midArray);
console.log(binTree);

重构后的二叉树应该是长这样的:

img8
阅读全文

← 根据前序、中序求后序 →