首页 > 代码库 > 【leetcode刷题笔记】Construct Binary Tree from Preorder and Inorder Traversal
【leetcode刷题笔记】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.
类似http://www.cnblogs.com/sunshineatnoon/p/3854935.html
只是子树的前序和中序遍历序列分别更新为：
//左子树：left_prestart = prestart+1left_preend = prestart+index-instart//右子树right_prestart = prestart+index-instart+1right_preend = preend
代码如下：
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 int InorderIndex(int[] inorder,int key){12 if(inorder == null || inorder.length == 0)13 return -1;14 15 for(int i = 0;i < inorder.length;i++)16 if(inorder[i] == key)17 return i;18 19 return -1;20 }21 public TreeNode buildTreeRec(int[] preoder,int[] inorder,int prestart,int preend,int instart,int inend){22 if(instart > inend)23 return null;24 TreeNode root = new TreeNode(preoder[prestart]);25 int index = InorderIndex(inorder, root.val);26 root.left = buildTreeRec(preoder, inorder, prestart+1, prestart+index-instart, instart, index-1);27 root.right = buildTreeRec(preoder, inorder, prestart+index-instart+1, preend, index+1, inend);28 29 return root;30 }31 public TreeNode buildTree(int[] preorder, int[] inorder) {32 return buildTreeRec(preorder, inorder, 0, preorder.length-1, 0, inorder.length-1);33 }34 }
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。