写点什么

LeetCode 题解:105. 从前序与中序遍历序列构造二叉树,递归 + 使用索引,JavaScript,详细注释

用户头像
Lee Chen
关注
发布于: 2021 年 01 月 14 日
LeetCode题解:105. 从前序与中序遍历序列构造二叉树,递归+使用索引,JavaScript,详细注释

原题连接:https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/


解题思路:


  1. 参考了多种解法,逐渐优化(补充国外大佬解法)和[动画演示 105. 从前序与中序遍历序列构造二叉树](https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/solution/dong-hua-yan-shi-105-cong-qian-xu-yu-zhong-xu-bian/)。

  2. 假设有一个二叉树如下:


	      1	    /   \	   2     3	  / \   / \ 	 4   5 6   7
复制代码


前序遍历的结果是: [1,2,4,5,3,6,7]

中序遍历的结果是: [4,2,5,1,6,3,7]


  1. 可以将其从根节点 1,拆分成两个子树,如下:


左子树:


	   2	  / \	 4   5
复制代码


前序遍历的结果是: [2,4,5]

中序遍历的结果是: [4,2,5]


右子树:


	   3	  / \ 	 6   7
复制代码


前序遍历的结果是: [3,6,7]

中序遍历的结果是: [6,3,7]


  1. 我们可以按照步骤 3 的规律,计算出左右子树的前中序遍历对应在原数组中的索引,即可知道它们对应的值:


* 左子树的前序遍历索引:


```

preLeft = preLeft + 1, // 左子树的前序遍历左边界

preRight = preLeft + nodeCount, // 当前左边界加上子树节点数量,即为左子树的前序遍历右边界

```


* 左子树的中序遍历索引:


```

inLeft = inLeft, // 左子树的中序遍历左边界

inRight = rootIndex - 1, // 左子树的中序遍历右边界

```


* 右子树的前序遍历索引:


```

preLeft = preLeft + nodeCount + 1, // 当前左边界加上子树节点数量再加 1,即为右子树的前序遍历左边界

preRight = preRight, // 右子树的前序遍历右边界

```


* 右子树的中序遍历索引:


```

inLeft = rootIndex + 1, // 右子树的中序遍历左边界

inRight = inRight, // 右子树的中序遍历右边界

```


  1. 经过步骤 4 的分析,我们可以按照以下逻辑进行递归:


* 每次递归用preorder[preLeft]的值生成一个根节点。

* 在通过preorder[preLeft]找到其在inorder中的位置rootIndex,计算出子树的前中序遍历在原数组中的索引,分别进行下一层的递归。

* 将下层递归生成的左右子树,连接到当前根节点上。

* 递归完成时将当前根节点返回,供上一层递归连接。

* preorderinorder中的所有值都生成过节点之后,也就完成了整个二叉树的生成。


/** * @param {number[]} preorder * @param {number[]} inorder * @return {TreeNode} */var buildTree = function (preorder, inorder) {  /**   * @description 使用前中序遍历结果的片段,递归生成二叉树   * @param {number} preLeft // 每个子树在前序遍历中的左边界   * @param {number} preRight // 每个子树在前序遍历中的右边界   * @param {number} inLeft // 每个子树在中序遍历中的左边界   * @param {number} inRight // 每个子树在中序遍历中的右边界   * @return {TreeNode}   */  function buildBinaryTree(preLeft, preRight, inLeft, inRight) {    // 当截取数组片段的左边界大于右边界时,表示当前用于构造子树的数组为空,退出循环    if (preLeft > preRight) {      // 数组为空时,表示当前已经无节点需要生成,返回null      // 让上一层节点的left和right指针指向null      return null;    }
// 缓存根节点的值 const rootVal = preorder[preLeft]; // 使用当前值创建一个节点,即为一个树的根节点 const root = new TreeNode(rootVal); // 查找到当前根节点在数组中的位置 const rootIndex = inorder.indexOf(rootVal); // 中序遍历的左边界到根节点之差是子树的节点数量 // 由于左边界始终会存在,因此向左统计总是可以得到子树的节点数量 const nodeCount = rootIndex - inLeft;
// 计算数组对应左子树的索引,向下递归 // 将当前根节点与已生成好的左子树连接 root.left = buildBinaryTree( preLeft + 1, // 左子树的前序遍历左边界 preLeft + nodeCount, // 当前左边界加上子树节点数量,即为左子树的前序遍历右边界 inLeft, // 左子树的中序遍历左边界 rootIndex - 1, // 左子树的中序遍历右边界 ); // 计算数组对应右子树的索引,向下递归 // 将当前根节点与已生成好的右子树连接 root.right = buildBinaryTree( preLeft + nodeCount + 1, // 当前左边界加上子树节点数量再加1,即为右子树的前序遍历左边界 preRight, // 右子树的前序遍历右边界 rootIndex + 1, // 右子树的中序遍历左边界 inRight, // 右子树的中序遍历右边界 );
// 将根节点返回供上层节点连接 return root; }
// 生成二叉树并返回 return buildBinaryTree(0, preorder.length - 1, 0, preorder.length - 1);};
复制代码


发布于: 2021 年 01 月 14 日阅读数: 13
用户头像

Lee Chen

关注

还未添加个人签名 2018.08.29 加入

还未添加个人简介

评论

发布
暂无评论
LeetCode题解:105. 从前序与中序遍历序列构造二叉树,递归+使用索引,JavaScript,详细注释