leetcode105~Construct Binary Tree from Preorder and Inorder Traversal

本文主要是介绍leetcode105~Construct Binary Tree from Preorder and Inorder Traversal，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Given preorder and inorder traversal of a tree, construct the binary tree.

Note:
You may assume that duplicates do not exist in the tree.

根据前序遍历和中序遍历可以唯一的确定一棵二叉树
代码如下，使用递归

public static TreeNode buildTree(int[] preorder, int[] inorder) {int preLength = preorder.length;int inLength = inorder.length;return helper(preorder,0,preLength-1,inorder,0,inLength-1);}private static TreeNode helper(int[] preorder, int preStart, int preEnd, int[] inorder, int inStart, int inEnd) {if(inStart>inEnd || preStart>preEnd) {return null;}int rootVal = preorder[preStart];int rootIndex = 0;for(int i=0;i<=inEnd;i++) {if(inorder[i] == rootVal) {rootIndex = i;break;}}int len = rootIndex-inStart;TreeNode root = new TreeNode(rootVal);root.left = helper(preorder,preStart+1,preStart+len,inorder,inStart,rootIndex-1);root.right = helper(preorder,preStart+len+1,preEnd,inorder,rootIndex+1,inEnd);return root;}

这篇关于leetcode105~Construct Binary Tree from Preorder and Inorder Traversal的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---