Construct Binary Tree from Preorder and Inorder Traversal
程序员文章站
2022-06-18 17:47:07
...
经典问题,通过先序序列和中序序列来构造一个二叉树;
要抓住的点就是先序序列中,首元素就是需要构造树的根元素。所以采用递归的方法,判断左子树和右子树序列,然后再次递归再次判定。这次题目遇到了Runtime的问题,总的来说是只需要从preorder中找第一个节点做根节点,从inorder序列中找左右子树就可以。
/**
* 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, 0, inorder.length - 1, preorder, inorder);
}
public TreeNode helper(int preStart, int inStart, int inEnd, int[] preorder, int[] inorder) {
if (preStart > preorder.length - 1 || inStart > inEnd) {
return null;
}
TreeNode root = new TreeNode(preorder[preStart]);
int inIndex = 0; // Index of current root in inorder
for (int i = inStart; i <= inEnd; i++) {
if (inorder[i] == root.val) {
inIndex = i;
}
}
root.left = helper(preStart + 1, inStart, inIndex - 1, preorder, inorder);
root.right = helper(preStart + inIndex - inStart + 1, inIndex + 1, inEnd, preorder, inorder);
return root;
}
}
推荐阅读
-
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
-
算法系列——Binary Tree Preorder Traversal
-
Binary Tree Preorder Traversal
-
LeetCode(106)Construct Binary Tree from Inorder and Postorder Traversal
-
中序遍历 94. Binary Tree Inorder Traversal