תיאור השאלה
Given the root of a binary tree, return the inorder traversal of its nodes' values (left subtree, node, right subtree).
איך פותרים?
אפשר ברקורסיה, אבל בראיון כדאי להראות את הגרסה האיטרטיבית: יורדים שמאלה ודוחפים למחסנית, שולפים צומת, מוסיפים את הערך שלו לתוצאה, ועוברים לבן הימני. סיבוכיות: O(n).
פתרון קוד
JavaScript
Python
function inorderTraversal(root) {
const result = [];
const stack = [];
let node = root;
while (node || stack.length) {
while (node) {
stack.push(node);
node = node.left;
}
node = stack.pop();
result.push(node.val);
node = node.right;
}
return result;
}
לעבור את ראיון העבודה הבא שלך בהצלחה
קורס דיגיטלי מקיף עם +25 שיעורים מעשיים, כשעתיים של וידאו, וליווי של מראיין בכיר.