AI solution for JavaScript Coding Question on BFE.dev
137. binary tree vertical traversal
One possible solution to this problem is to use a hash table to store the nodes by their horizontal positions, and a priority queue to sort the nodes within each horizontal position based on their vertical positions inherited from their parent nodes.
Here's the JavaScript code:
/**
- Definition for a binary tree node.
- function TreeNode(val, left, right) {
-
this.val = (val===undefined ? 0 : val)
-
this.left = (left===undefined ? null : left)
-
this.right = (right===undefined ? null : right)
- } */
/**
-
@param {TreeNode} root
-
@return {number[]} */ var verticalTraversal = function(root) { const hash = new Map(); const queue = [[root, 0, 0]];
while (queue.length > 0) { const [node, x, y] = queue.shift(); if (!hash.has(x)) { hash.set(x, []); } const nodes = hash.get(x); nodes.push([node.val, y]); if (node.left) { queue.push([node.left, x - 1, y + 1]); } if (node.right) { queue.push([node.right, x + 1, y + 1]); } }
const keys = Array.from(hash.keys()).sort((a, b) => a - b); const result = []; for (const key of keys) { const nodes = hash.get(key); nodes.sort((a, b) => { if (a[1] !== b[1]) { return a[1] - b[1]; } else { return a[0] - b[0]; } }); nodes.forEach(n => result.push(n[0])); }
return result; };