105. Construct Binary Tree from Preorder and Inorder Traversal
程序员文章站
2022-03-03 10:13:17
...
Given preorder and inorder traversal of a tree, construct the binary tree.
Note:
You may assume that duplicates do not exist in the tree.
For example, given
preorder = [3,9,20,15,7]
inorder = [9,3,15,20,7]
Return the following binary tree:
3
/ \
9 20
/ \
15 7
Solution
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode buildTree(int[] preorder, int[] inorder) {
return helper(0, preorder.length - 1, 0, inorder.length - 1, preorder, inorder);
}
public TreeNode helper(int preStart, int preEnd, int inStart, int inEnd, int[] preorder, int[] inorder){
if (preStart > preEnd || inStart > inEnd){
return null;
}
TreeNode root = new TreeNode(preorder[preStart]);
int inIndex = 0;
for (int i = inStart; i <= inEnd; i++){
if (inorder[i] == root.val){
inIndex = i;
}
}
root.left = helper(preStart + 1, preEnd, inStart, inIndex - 1, preorder, inorder);
root.right = helper(preStart + 1 + inIndex - inStart, preEnd, inIndex + 1, inEnd, preorder, inorder);
return root;
}
}
上一篇: 数据结构,操作系统,计算机网络,计算机组成原理这几门课在大学生计算机专业知识体系中有怎样的地位?
下一篇: 105. Construct Binary Tree from Preorder and Inorder Traversal
推荐阅读
-
LeetCode 105 Construct Binary Tree from Preorder and Inorder Traversal
-
LeetCode: 105. Construct Binary Tree from Preorder and Inorder Traversal
-
leetcode 随笔 Construct Binary Tree from Preorder and Inorder Traversal
-
105. Construct Binary Tree from Preorder and Inorder Traversal
-
Construct Binary Tree from Preorder and Inorder Traversal
-
Construct Binary Tree from Preorder and Inorder Traversal
-
LeetCode(106)Construct Binary Tree from Inorder and Postorder Traversal
-
105. Construct Binary Tree from Preorder and Inorder Traversal
-
LeetCode106. Construct Binary Tree from Inorder and Postorder Traversal
-
105. Construct Binary Tree from Preorder and Inorder Traversal