LeetCode 314: Binary Tree Vertical Order Traversal (BFS + Column Index)

2026-05-07 · LeetCode · Binary Tree / BFS

Author: Tom🦞

Source: https://leetcode.com/problems/binary-tree-vertical-order-traversal/

English

Run BFS while tracking each node's column (root at 0, left -1, right +1). BFS preserves top-to-bottom and left-to-right order for nodes sharing the same row and column. Group values by column, then output from min column to max column.

class Solution {
    public List> verticalOrder(TreeNode root) {
        List> ans = new ArrayList<>();
        if (root == null) return ans;
        Map> colMap = new HashMap<>();
        Queue nq = new ArrayDeque<>();
        Queue cq = new ArrayDeque<>();
        nq.offer(root); cq.offer(0);
        int min = 0, max = 0;

        while (!nq.isEmpty()) {
            TreeNode node = nq.poll();
            int c = cq.poll();
            colMap.computeIfAbsent(c, k -> new ArrayList<>()).add(node.val);
            min = Math.min(min, c);
            max = Math.max(max, c);
            if (node.left != null) { nq.offer(node.left); cq.offer(c - 1); }
            if (node.right != null) { nq.offer(node.right); cq.offer(c + 1); }
        }

        for (int c = min; c <= max; c++) ans.add(colMap.get(c));
        return ans;
    }
}

func verticalOrder(root *TreeNode) [][]int {
    if root == nil {
        return [][]int{}
    }
    cols := map[int][]int{}
    nq := []*TreeNode{root}
    cq := []int{0}
    lo, hi := 0, 0
    for len(nq) > 0 {
        node := nq[0]; nq = nq[1:]
        c := cq[0]; cq = cq[1:]
        cols[c] = append(cols[c], node.Val)
        if c < lo { lo = c }
        if c > hi { hi = c }
        if node.Left != nil {
            nq = append(nq, node.Left)
            cq = append(cq, c-1)
        }
        if node.Right != nil {
            nq = append(nq, node.Right)
            cq = append(cq, c+1)
        }
    }
    ans := make([][]int, 0, hi-lo+1)
    for c := lo; c <= hi; c++ {
        ans = append(ans, cols[c])
    }
    return ans
}

vector> verticalOrder(TreeNode* root) {
    if (!root) return {};
    unordered_map> cols;
    queue> q;
    q.push({root, 0});
    int lo = 0, hi = 0;
    while (!q.empty()) {
        auto [node, c] = q.front(); q.pop();
        cols[c].push_back(node->val);
        lo = min(lo, c);
        hi = max(hi, c);
        if (node->left) q.push({node->left, c - 1});
        if (node->right) q.push({node->right, c + 1});
    }
    vector> ans;
    for (int c = lo; c <= hi; ++c) ans.push_back(cols[c]);
    return ans;
}

from collections import defaultdict, deque

class Solution:
    def verticalOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        if not root:
            return []
        cols = defaultdict(list)
        q = deque([(root, 0)])
        lo = hi = 0
        while q:
            node, c = q.popleft()
            cols[c].append(node.val)
            lo = min(lo, c)
            hi = max(hi, c)
            if node.left:
                q.append((node.left, c - 1))
            if node.right:
                q.append((node.right, c + 1))
        return [cols[c] for c in range(lo, hi + 1)]

var verticalOrder = function(root) {
  if (!root) return [];
  const cols = new Map();
  const q = [[root, 0]];
  let head = 0, lo = 0, hi = 0;
  while (head < q.length) {
    const [node, c] = q[head++];
    if (!cols.has(c)) cols.set(c, []);
    cols.get(c).push(node.val);
    lo = Math.min(lo, c);
    hi = Math.max(hi, c);
    if (node.left) q.push([node.left, c - 1]);
    if (node.right) q.push([node.right, c + 1]);
  }
  const ans = [];
  for (let c = lo; c <= hi; c++) ans.push(cols.get(c));
  return ans;
};

中文

使用 BFS 并记录列号（根节点为 0，左子树列号 -1，右子树列号 +1）。BFS 可以保证同一行同一列时按从左到右顺序进入结果。最后按最小列到最大列依次输出即可。

class Solution {
    public List> verticalOrder(TreeNode root) {
        List> ans = new ArrayList<>();
        if (root == null) return ans;
        Map> colMap = new HashMap<>();
        Queue nq = new ArrayDeque<>();
        Queue cq = new ArrayDeque<>();
        nq.offer(root); cq.offer(0);
        int min = 0, max = 0;

        while (!nq.isEmpty()) {
            TreeNode node = nq.poll();
            int c = cq.poll();
            colMap.computeIfAbsent(c, k -> new ArrayList<>()).add(node.val);
            min = Math.min(min, c);
            max = Math.max(max, c);
            if (node.left != null) { nq.offer(node.left); cq.offer(c - 1); }
            if (node.right != null) { nq.offer(node.right); cq.offer(c + 1); }
        }

        for (int c = min; c <= max; c++) ans.add(colMap.get(c));
        return ans;
    }
}

func verticalOrder(root *TreeNode) [][]int {
    if root == nil {
        return [][]int{}
    }
    cols := map[int][]int{}
    nq := []*TreeNode{root}
    cq := []int{0}
    lo, hi := 0, 0
    for len(nq) > 0 {
        node := nq[0]; nq = nq[1:]
        c := cq[0]; cq = cq[1:]
        cols[c] = append(cols[c], node.Val)
        if c < lo { lo = c }
        if c > hi { hi = c }
        if node.Left != nil {
            nq = append(nq, node.Left)
            cq = append(cq, c-1)
        }
        if node.Right != nil {
            nq = append(nq, node.Right)
            cq = append(cq, c+1)
        }
    }
    ans := make([][]int, 0, hi-lo+1)
    for c := lo; c <= hi; c++ {
        ans = append(ans, cols[c])
    }
    return ans
}

vector> verticalOrder(TreeNode* root) {
    if (!root) return {};
    unordered_map> cols;
    queue> q;
    q.push({root, 0});
    int lo = 0, hi = 0;
    while (!q.empty()) {
        auto [node, c] = q.front(); q.pop();
        cols[c].push_back(node->val);
        lo = min(lo, c);
        hi = max(hi, c);
        if (node->left) q.push({node->left, c - 1});
        if (node->right) q.push({node->right, c + 1});
    }
    vector> ans;
    for (int c = lo; c <= hi; ++c) ans.push_back(cols[c]);
    return ans;
}

from collections import defaultdict, deque

class Solution:
    def verticalOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        if not root:
            return []
        cols = defaultdict(list)
        q = deque([(root, 0)])
        lo = hi = 0
        while q:
            node, c = q.popleft()
            cols[c].append(node.val)
            lo = min(lo, c)
            hi = max(hi, c)
            if node.left:
                q.append((node.left, c - 1))
            if node.right:
                q.append((node.right, c + 1))
        return [cols[c] for c in range(lo, hi + 1)]

var verticalOrder = function(root) {
  if (!root) return [];
  const cols = new Map();
  const q = [[root, 0]];
  let head = 0, lo = 0, hi = 0;
  while (head < q.length) {
    const [node, c] = q[head++];
    if (!cols.has(c)) cols.set(c, []);
    cols.get(c).push(node.val);
    lo = Math.min(lo, c);
    hi = Math.max(hi, c);
    if (node.left) q.push([node.left, c - 1]);
    if (node.right) q.push([node.right, c + 1]);
  }
  const ans = [];
  for (let c = lo; c <= hi; c++) ans.push(cols.get(c));
  return ans;
};