首页 > 代码库 > Construct Binary Tree from Preorder and Inorder Traversal
Construct Binary Tree from Preorder and Inorder Traversal
Given preorder and inorder traversal of a tree, construct the binary tree.
这道题是要根据先序遍历和中序遍历构造出一棵二叉树，这道题和上一题是一样的。上一题不过是通过后序遍历和中序遍历构造一棵二叉树。
只要将代码稍稍修改即可
1 public class Solution { 2 public TreeNode buildTree(int[] preorder, int[] inorder) { 3 TreeNode root; 4 if(preorder.length == 0) 5 return null; 6 return createTree(preorder, inorder, 0, preorder.length - 1, 0, inorder.length - 1); 7 8 } 9 private TreeNode createTree(int[] preorder, int[] inorder, int preStart, int preEnd, int inStart ,int inEnd){10 if(inStart > inEnd)11 return null;12 int value_root = preorder[preStart]; //根据先序遍历第一个元素为根节点,找出根节点的值13 int index = 0; //根节点在中序遍历中的索引值14 for(int i = inStart; i <= inEnd; i++){ //查找根节点在中序遍历中的索引值15 if(value_root == inorder[i]){16 index = i;17 break;18 }19 }//for20 int length_leftTree = index - inStart; //左子树的长度21 TreeNode root_left = createTree(preorder, inorder, preStart + 1, preStart + length_leftTree, inStart, index - 1);22 TreeNode root_right = createTree(preorder, inorder, preStart + length_leftTree + 1, preEnd, index + 1, inEnd);23 24 TreeNode root = new TreeNode(value_root);25 root.left = root_left;26 root.right = root_right;27 28 return root;29 }30 }
Construct Binary Tree from Preorder and Inorder Traversal
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。