בינוניLeetCode #105
Construct Binary Tree from Preorder and Inorder Traversal
תיאור השאלה
Given two integer arrays preorder and inorder, the preorder and inorder traversals of the same binary tree with unique values, construct and return the binary tree.
איך פותרים?
האיבר הבא ב־preorder הוא תמיד השורש של תת־העץ הנוכחי. מוצאים את המיקום שלו ב־inorder (בעזרת מפה, ב־O(1)): כל מה שמשמאלו הוא תת־העץ השמאלי וכל מה שמימינו הוא הימני. בונים קודם את השמאלי ואחר כך את הימני. סיבוכיות: O(n).
פתרון קוד
JavaScript
Python
function buildTree(preorder, inorder) {
const indexOf = new Map(inorder.map((value, i) => [value, i]));
let preIndex = 0;
function build(left, right) {
if (left > right) return null;
const rootVal = preorder[preIndex++];
const mid = indexOf.get(rootVal);
const root = new TreeNode(rootVal);
root.left = build(left, mid - 1);
root.right = build(mid + 1, right);
return root;
}
return build(0, inorder.length - 1);
}
לעבור את ראיון העבודה הבא שלך בהצלחה
קורס דיגיטלי מקיף עם +25 שיעורים מעשיים, כשעתיים של וידאו, וליווי של מראיין בכיר.