剑指offer 07.重建二叉树 | 刷题打卡

题目描述

输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

例如，给出

前序遍历 preorder = [3,9,20,15,7] 中序遍历 inorder = [9,3,15,20,7] 返回如下的二叉树：

    3
   / \
  9  20
    /  \
   15   7

限制：

0 <= 节点个数 <= 5000

解题思路

对于一个二叉树来说，前序遍历的第一个元素就是二叉树的父节点，我们可以根据父节点找到父节点在中序遍历中的位置index，根据index我们就可以将 中序遍历分为左右两个子树，这两个子树也是中序遍历。根据index我们也可以找到左子树和右子树的前序遍历。这是我们就可以得到四个数组，分别是中序遍历的左子树和右子树，前序遍历的左子树和右子树，所以我们就可以递归地调用函数，分别去找左子树和右子树的父节点，找到后赋值给node.left和node.right。结束递归的条件就是前序遍历的数组只有一个元素，说明只有根元素，左右子树为空，就返回这个节点。

AC代码

/* 
前序遍历：跟节点 + 左子树前序遍历 + 右子树前序遍历
中序遍历：左子树中序遍历 + 跟节点 + 右字数中序遍历
后序遍历：左子树后序遍历 + 右子树后序遍历 + 跟节点
根据上面的规律：

前序遍历找到根结点root
找到root在中序遍历的位置 -> 左子树的长度和右子树的长度
截取左子树的中序遍历、右子树的中序遍历
截取左子树的前序遍历、右子树的前序遍历
递归重建二叉树
*/
class Node {
    constructor(data, left, right) {
        this.data = data;
        this.left = left;
        this.right = right
    }
    show() {
        console.log(this.data);
    }
};

 function rebuildTree(pre,mid) {
    if (pre.length === 0) {
        return null;
    }
    if (pre.length === 1) {
        return new Node(pre[0])
    }
    const data = pre[0];
    const index = mid.indexOf(data);
    const midLeft = mid.slice(0,index);
    const midRight = mid.slice(index+1);
    const preLeft = pre.slice(1,index+1);
    const preRight = pre.slice(index+1);
    const node = new Node(data);
    node.left = rebuildTree(preLeft,midLeft);
    node.right = rebuildTree(preRight,midRight);
    return node;
 }
 let preorder = [3,9,20,15,7];
 let inorder = [9,3,15,20,7];
console.log( rebuildTree(preorder,inorder));

总结

对于任意一颗树而言，前序遍历的形式总是

[ 根节点, [左子树的前序遍历结果], [右子树的前序遍历结果] ]

即根节点总是前序遍历中的第一个节点。而中序遍历的形式总是

[ [左子树的中序遍历结果], 根节点, [右子树的中序遍历结果] ]

只要我们在中序遍历中定位到根节点，那么我们就可以分别知道左子树和右子树中的节点数目。由于同一颗子树的前序遍历和中序遍历的长度显然是相同的，因此我们就可以对应到前序遍历的结果中，对上述形式中的所有左右括号进行定位。

这样以来，我们就知道了左子树的前序遍历和中序遍历结果，以及右子树的前序遍历和中序遍历结果，我们就可以递归地对构造出左子树和右子树，再将这两颗子树接到根节点的左右位置。

本文正在参与「掘金 2021 春招闯关活动」, 点击查看 活动详情