987. Vertical Traversal

BFS还是非常重要滴

尽管使用频率与知名度 不能和与递归挂勾的DFS相比

可BFS在树和图论的层级遍历上 仍是有其精妙之处

绝对不能让自己在俩搜索法只懂其中一边

若对BFS不够熟的话 先看下GeeksforGeeks这篇

掌握了BFS基本原理后 再来做987号题

Vertical Order Traversal of a Binary Tree

虽然此题是Hard 可我还是会说

987号题是广度优先搜索的好暖身之处😉😏

二叉树的行列坐标

题目有说 任何一个父节点坐标若为$(x, y)$

它的左右子节点分别是$(x + 1, y - 1)$和$(x + 1, y + 1)$

非常浅显易懂 父往左子是向左下滑 于是行数加1 列数减1

父往右子是向右下滑 行数同样加1 列数却是因此反过来要加1

树根的坐标自然是$(0, 0)$ 毕竟树根站在 中路 嘛

节点排序原则：先按列升序 同列按值升序

分各列追踪

此乃题目给我们的设定 又结合二叉树的特性

每往下走一层 列必然向左扩张

向右的延伸则要看情况而定 由此可见

能采取广度优先搜索这种层层下挖的风格 让我们解决本题

首先自然要准备个数组columnsValues

其由左到右存储着给二叉树由左到右每一列的专属数组

专属数祖上 存放该列中升序后的全部节点值

因此呢 关键仅在于

朝节点广度搜索的同时要记录

目前columnsValues储存的最左列 是二叉树上的几号列？

还有储存的最右列 又是二叉树上的几号列？

一旦BFS访问到的节点之列 比储存的最左列值leftmostCol还左

columnsValues必须在最左边插入一个空数组

空数组储存新的最左列之对应节点值

反过来 倘若是比储存的最右列值rightmostCol还右

columnsValues必须在最右边插入一个空数组

空数组储存新的最右列之对应节点值

能左能右 也是没谁咯

我们得知 columnsValues必须能兼具最左与最右的插入能力

于是答案呼之欲出 双端队列便是我们columnsValues的根基

左右延伸后的columnsValues索引定位

肯定会有人好奇 如果columnsValues能向左扩张

这样要如何靠索引准确定位 某个树节点究竟该放哪儿？

我让各位自己先停在这儿好好想明白 再往下读～～

远在天边 近在眼前

没错 就是leftmostCol来做基准啰

既然leftmostCol储存当前columnsValues的最左列值

那么任何目前访问到的列值 减去leftmostCol

不就是该列在columnsValues中的索引位置嘛🤓😎

搜集完全部的列与节点后

别忘记各列中节点值还要进行升序排序齁

内部排序好后 即可回传 毕竟外部早就排序完毕唷

C++

#include <queue>
#include <vector>
using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;

    TreeNode()
        : val(0)
        , left(nullptr)
        , right(nullptr) {}

    TreeNode(int x)
        : val(x)
        , left(nullptr)
        , right(nullptr) {}

    TreeNode(int x, TreeNode* left, TreeNode* right)
        : val(x)
        , left(left)
        , right(right) {}
};

vector<vector<int>> findVerticalTraversal(TreeNode* root) {
    // Each tuple format: {tree node, row, column}.
    deque<tuple<TreeNode*, int, int>> queue = {{root, 0, 0}};

    // Each tuple format: {row, value}.
    deque<vector<tuple<int, int>>> columnsValues = {{}};

    int leftmostCol = 0, rightmostCol = 0;

    while (!queue.empty()) {
        auto [node, row, column] = queue.front();
        queue.pop_front();

        if (column < leftmostCol) {
            leftmostCol = column;
            columnsValues.push_front({});
        }

        if (column > rightmostCol) {
            rightmostCol = column;
            columnsValues.push_back({});
        }

        columnsValues[column - leftmostCol].push_back({row, node->val});

        if (node->left != nullptr)
            queue.push_back({node->left, row + 1, column - 1});

        if (node->right != nullptr)
            queue.push_back({node->right, row + 1, column + 1});
    }

    vector<vector<int>> verticalTraversal = {};

    for (auto columnValues : columnsValues) { // Need to sort so no const.
        verticalTraversal.push_back({});

        sort(columnValues.begin(), columnValues.end());
        for (const auto& [row, value] : columnValues)
            verticalTraversal.back().push_back(value);
    }

    return verticalTraversal;
}

Python

from collections import deque


class TreeNode:
    def __init__(self, val=0, left=None, right=None) -> None:
        self.val = val
        self.left = left
        self.right = right


def find_vertical_traversal(root: TreeNode) -> list[list[int]]:
    # Each tuple format: (tree node, row, column).
    queue: deque[tuple[TreeNode, int, int]] = deque([(root, 0, 0)])

    # Each tuple format: (row, value).
    columns_values: deque[list[tuple[int, int]]] = deque([[]])

    leftmost_col, rightmost_col = 0, 0

    while queue:
        node, row, column = queue.popleft()

        if column < leftmost_col:
            leftmost_col = column
            columns_values.appendleft([])

        if column > rightmost_col:
            rightmost_col = column
            columns_values.append([])

        columns_values[column - leftmost_col].append((row, node.val))

        if node.left:
            queue.append((node.left, row + 1, column - 1))
        if node.right:
            queue.append((node.right, row + 1, column + 1))

    vertical_traversal: list[list[int]] = []

    for column_values in columns_values:
        vertical_traversal.append([])

        column_values.sort()
        for _, value in column_values:
            vertical_traversal[-1].append(value)

    return vertical_traversal

空间复杂度是$O(n)$ $n$是二叉树中的节点数

本就是BFS那先进先出的队列的空间特性

时间复杂度$O(nlogn)$ 因为有排序的关系