首页 > 代码库 > 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.
Note:
You may assume that duplicates do not exist in the tree.
方法
根据树的中序遍历和前序遍历,来构造树,使用递归的思想。TreeNode getTree(int[] preorder, int preStart, int preEnd, int[] inorder, int inStart, int inEnd) { if (preStart >= preEnd) { return null; } int cur = preorder[preStart]; TreeNode root = new TreeNode(cur); int i = 0; int j = inStart; while(inorder[j] != cur) { j++; i++; } root.left = getTree(preorder, preStart + 1, preStart + i + 1, inorder, inStart, inStart + i); root.right = getTree(preorder, preStart + i + 1, preEnd, inorder, inStart + i + 1, inEnd); return root; } public TreeNode buildTree(int[] preorder, int[] inorder) { if (preorder == null) { return null; } int len = preorder.length; return getTree(preorder, 0, len, inorder, 0, len); }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。