首页 > 代码库 > leetcode 105 Construct Binary Tree from Preorder and Inorder Traversal ----- java
leetcode 105 Construct Binary Tree from Preorder and Inorder Traversal ----- java
Given preorder and inorder traversal of a tree, construct the binary tree.
Note:
You may assume that duplicates do not exist in the tree.
给出前序遍历和中序遍历,然后求这棵树。
很有规律。递归就可以实现。
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class Solution { public TreeNode buildTree(int[] preorder, int[] inorder) { int len = preorder.length; if( len == 0) return null; return helper(preorder,0,len-1,inorder,0,len-1); } public TreeNode helper( int[] preorder,int pre_start,int pre_end,int[] inorder,int in_start,int in_end){ if( pre_start > pre_end || in_start > in_end ) return null; TreeNode node = new TreeNode(preorder[pre_start]); int size = 0; for( int i = in_start;i<=in_end && inorder[i] != preorder[pre_start];i++,size++) ; node.left = helper(preorder,pre_start+1,pre_start+size,inorder,in_start,in_start+size-1); node.right = helper(preorder,pre_start+size+1,pre_end,inorder,in_start+size+1,in_end); return node; } }
速度不算快,速度最快的答案也进行了参考。
并不是算法有多好,只是他在
for( int i = in_start;i<=in_end && inorder[i] != preorder[pre_start];i++,size++) ;
这里遍历的时候选择了从后向前遍历,由于测试数据的特殊性,导致了其答案的快速性。
leetcode 105 Construct Binary Tree from Preorder and Inorder Traversal ----- java
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。