首页 > 代码库 > [leetcode]105. Construct Binary Tree from Preorder and Inorder Traversal
[leetcode]105. 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.
根据二叉树的前序遍历和中序遍历形成的数组，还原出二叉树 ，二叉树中没有重复的元素
思路：前序遍历数组有特点：数组的每个数都是接下来几个数的根节点，和后边几个数构成子树，只要知道每棵子树节点的个数，就可以知道每棵树的根节点
中序遍历数组有特点：根节点总是在中间，两边分别是左子树和右子树，只要知道根节点，就能回到左子树和右子树的区间个节点个数
根据这两个特点，可以递归构建所有子树，最后返回的就是整个树
public TreeNode buildTree(int[] preorder, int[] inorder) { return build(preorder,0,preorder.length-1,inorder,0,inorder.length-1); } public TreeNode build(int[] preorder,int preSta,int preEnd,int[] inorder,int inSta,int inEnd) { //到叶节点返回 if (preSta > preEnd || inSta > inEnd) { return null; } else { //获取此次的根节点下标 int index = 0; for (int i = inSta; i <= inEnd; i++) { if (inorder[i] == preorder[preSta]) { index = i; break; } } //左子树和右子树的长度 int len1 = index - inSta-1; int len2 = inEnd - index-1; //当前树 TreeNode cur = new TreeNode(preorder[preSta]); //当前树的左右子树又递归求得 cur.left = build(preorder,preSta+1,preSta+1+len1,inorder,inSta,index-1); cur.right = build(preorder,preEnd-len2,preEnd,inorder,index+1,inEnd); return cur; } }
[leetcode]105. Construct Binary Tree from Preorder and Inorder Traversal
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。