递归法从前序与中序遍历序列构造二叉树

105. 从前序与中序遍历序列构造二叉树

思路

需要明白的知识点有：

• 中序遍历中一个节点的左侧是它的左子树的所有节点，右侧是它的右子树的所有节点
• 前序遍历中的第一个节点是当前节点，其左子树和右子树均在其右侧

我们可以根据前续遍历找到当前节点，然后找到当前根节点在中序数组中的位置，进而由根节点的位置及其子树的范围确定新的左子树与右子树的范围，然后进行不断递归，直到最后遍历完整个数组。

我们无法确定前续遍历中左子树与右子树的范围，但是可以从中序遍历中获得这个值

具体请看32与33行

package cn.edu.xjtu.carlWay.tree.preAndInConstructBinaryTree;import cn.edu.xjtu.Util.TreeNode.TreeNode;/*** 105. 从前序与中序遍历序列构造二叉树* 给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。* 
* https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/*/
public class Solution {public TreeNode buildTree(int[] preorder, int[] inorder) {return helpBuild(preorder, 0, preorder.length, inorder, 0, inorder.length);}private TreeNode helpBuild(int[] preorder, int preLeft, int preRight, int[] inorder, int inLeft, int inRight) {if (inRight - inLeft == 0) {return null;}if (inRight - inLeft == 1) {return new TreeNode(inorder[inLeft]);}TreeNode root = new TreeNode(preorder[preLeft]);int rootIndex = 0;for (int i = inLeft; i < inRight; i++) {if (inorder[i] == root.val) {rootIndex = i;break;}}root.left = helpBuild(preorder, preLeft + 1, preLeft + 1 + (rootIndex - inLeft), inorder, inLeft, rootIndex);root.right = helpBuild(preorder, preLeft + 1 + (rootIndex - inLeft), preRight, inorder, rootIndex + 1, inRight);return root;}
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！