Open Yukibei opened 5 months ago
class Solution { public: vector<vector> verticalTraversal(TreeNode root) { vector<tuple<int, int, int>> data; function<void(TreeNode, int, int)> dfs = [&](TreeNode *node, int row, int col) { if (node == nullptr) { return; } data.emplace_back(col, row, node->val); dfs(node->left, row + 1, col - 1); dfs(node->right, row + 1, col + 1); }; dfs(root, 0, 0);
vector<vector<int>> ans; ranges::sort(data); int last_col = INT_MIN; for (auto &[col, _, val]: data) { if (col != last_col) { last_col = col; ans.push_back({}); } ans.back().push_back(val); } return ans; }
};
。 时间复杂度：O(nlogn)，其中 nnn 为二叉树的节点个数。瓶颈在排序上。 空间复杂度：O(n)。
class Solution { public: vector<vector> verticalTraversal(TreeNode root) {
vector<tuple<int, int, int>> data;
function<void(TreeNode, int, int)> dfs = [&](TreeNode *node, int row, int col) {
if (node == nullptr) {
return;
}
data.emplace_back(col, row, node->val);
dfs(node->left, row + 1, col - 1);
dfs(node->right, row + 1, col + 1);
};
dfs(root, 0, 0);
};
。 时间复杂度：O(nlogn)，其中 nnn 为二叉树的节点个数。瓶颈在排序上。 空间复杂度：O(n)。