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

本文主要是介绍leetcode105 从前序与中序遍历序列构造二叉树，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

根据一棵树的前序遍历与中序遍历构造二叉树。

注意:
你可以假设树中没有重复的元素。

例如，给出

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

返回如下的二叉树：

    3/ \9  20/  \15   7

 

class Solution {public TreeNode buildTree(int[] preorder, int[] inorder) {if (preorder.length == 0) {return null;}int curVal = preorder[0];TreeNode t = new TreeNode(curVal);t.left = t.right = null;int len = inorder.length;int mid = -1;for (int i = 0; i < len; i++) {if (inorder[i] == curVal) {mid = i;break;}}if (mid == -1) {return t;}int leftLen = mid - 0;if (leftLen >= 1) {int[] leftPreorder = new int[leftLen];int[] leftInorder = new int[leftLen];System.arraycopy(preorder, 1, leftPreorder, 0, leftLen);System.arraycopy(inorder, 0, leftInorder, 0, leftLen);t.left = buildTree(leftPreorder, leftInorder);}int rightLen = len - (mid + 1);if (rightLen >= 1) {int[] rightPreorder = new int[rightLen];int[] rightInorder = new int[rightLen];System.arraycopy(preorder, leftLen + 1, rightPreorder, 0, rightLen);System.arraycopy(inorder, mid + 1, rightInorder, 0, rightLen);t.right = buildTree(rightPreorder, rightInorder);}return t;}
}

 

这篇关于leetcode105 从前序与中序遍历序列构造二叉树的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---