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