首页 > 代码库 > Leetcode-Construct Binary Tree from inorder and preorder travesal
Leetcode-Construct Binary Tree from inorder and preorder travesal
Given preorder and inorder traversal of a tree, construct the binary tree.
Note:
You may assume that duplicates do not exist in the tree.
Solution:
1 /** 2 * Definition for binary tree 3 * public class TreeNode { 4 * int val; 5 * TreeNode left; 6 * TreeNode right; 7 * TreeNode(int x) { val = x; } 8 * } 9 */10 public class Solution {11 public TreeNode buildTree(int[] preorder, int[] inorder) {12 TreeNode root = buildTreeRecur(preorder,inorder,0,preorder.length-1,0,inorder.length-1);13 return root;14 }15 16 public TreeNode buildTreeRecur(int[] preorder, int[] inorder, int preS, int preE, int inS, int inE){17 if (preS>preE) return null;18 if (preS==preE){19 TreeNode leaf = new TreeNode(preorder[preS]);20 return leaf;21 }22 23 int rootVal = preorder[preS];24 int index = inS;25 for (int i=inS;i<=inE;i++)26 if (inorder[i]==rootVal){27 index = i;28 break;29 }30 31 int leftLen = index-inS;32 int rightLen = inE - index;33 34 TreeNode leftChild = buildTreeRecur(preorder,inorder,preS+1,preS+leftLen,inS,index-1);35 TreeNode rightChild = buildTreeRecur(preorder,inorder,preE-rightLen+1,preE,index+1,inE);36 TreeNode root = new TreeNode(rootVal);37 root.left = leftChild;38 root.right= rightChild;39 return root;40 }41 42 }
Construct Binary Tree from Preorder and Inorder Traversal
Leetcode-Construct Binary Tree from inorder and preorder travesal
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。