重建二叉树(中等) · yinshibanxian

01 Jun 2020 1101字 4分次
BY-SA 4.0（除特别声明或转载文章外）

一、题目描述

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

例如，给出

前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]

返回如下的二叉树

二、题目解析

递归法

根据前序遍历/后序遍历+中序遍历可以重建一棵二叉树，这道题考察的就是前序遍历+中序遍历重建二叉树.

对于:

 前序遍历 preorder = [3,9,20,15,7]
 中序遍历 inorder = [9,3,15,20,7]

前序遍历中的3即为根节点的值，由于输入的前序遍历和后序遍历的结果中都不含重复的数字，那么在中序遍历中，3

前面的节点都是左子树上的节点，3后面的节点都是右子树上的节点，这一步可以获得根节点和左右两个子树，再递归地对左右子树进行

重建，即可重建出整棵二叉树。

 /**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
 /**
 * @param {number[]} preorder
 * @param {number[]} inorder
 * @return {TreeNode}
 */
 var buildTree = function(preorder, inorder) {
     if(!preorder.length || !inorder.length) {
         return null;
     }
     const rootVal = preorder[0];
     const node = new TreeNode(rootVal);
     // index有两层含义，一是根节点在中序遍历中的次序，二是左子树节点的数量
     const index = inorder.indexOf(rootVal);
     // preorder.slice(1,index+1)是左子树的前序遍历
     // inorder.slice(0,index) 是左子树的中序遍历
     // 这一步递归的对左子树进行重建
     node.left = buildTree(preorder.slice(1,index+1),inorder.slice(0,index));
     node.right = buildTree(preorder.slice(index+1),inorder.slice(index+1))
     return node;
 };

时间复杂度: O(n)
空间复杂度: O(n)

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/zhong-jian-er-cha-shu-lcof

重建二叉树(中等) yinshibanxian

一、题目描述

二、题目解析