2023-06-06：给你二叉树的根结点 root ，请你设计算法计算二叉树的 垂序遍历 序列。
对位于 (row, col) 的每个结点而言，
其左右子结点分别位于 (row + 1, col – 1) 和 (row + 1, col + 1)
树的根结点位于 (0, 0) 。
二叉树的 垂序遍历 从最左边的列开始直到最右边的列结束，按列索引每一列上的所有结点，
形成一个按出现位置从上到下排序的有序列表。如果同行同列上有多个结点，
则按结点的值从小到大进行排序。
返回二叉树的 垂序遍历 序列。
输入：root = [3,9,20,null,null,15,7]。
输出：[[9],[3,15],[20],[7]]。
答案2023-06-06：
大体过程如下：
1 定义结构体TreeNode表示二叉树节点，包含属性Val表示节点值和Left和Right分别表示左右节点。
2.定义结构体Info表示节点信息，包含属性row、col和val分别表示节点所在的行、列和值。
3.定义函数NewInfo()创建节点信息。
4.定义切片类型ByColThenRowThenVal并实现其三个方法Len()、Less()和Swap()使之按列、行和节点值排序。
5.定义函数verticalTraversal()实现二叉树的垂序遍历。
6.在verticalTraversal()中，创建切片collects存储各节点信息，并将根节点的信息存入其中。
7.调用函数dfs()遍历整个二叉树，添加各节点的信息到collects中。
8.对collects按列、行和节点值排序。
9.遍历collects，将同列的所有节点值存入一个新的子切片，将子切片添加到答案ans中。
10.返回答案ans。
时间复杂度是O(nlogn)，其中n是节点数。n个节点需要遍历一次，排序时间复杂度是O(nlogn)。所以总时间复杂度是O(nlogn)。
空间复杂度是O(n)，其中n是节点数。需要使用切片collects来存储节点的信息，collects的长度最大是n，所以空间复杂度是O(n)。
golang完整代码如下：
package main
import (
"fmt"
"sort"
)
type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}
type Info struct {
row int
col int
val int
}
func NewInfo(r, c, v int) Info {
return Info{row: r, col: c, val: v}
}
type ByColThenRowThenVal []Info
func (bc ByColThenRowThenVal) Len() int { return len(bc) }
func (bc ByColThenRowThenVal) Less(i int, j int) bool {
if bc[i].col != bc[j].col {
return bc[i].col 
c++完整代码如下：
#include
#include
#include
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) {}
};
struct Info {
int row;
int col;
int val;
Info(int r, int c, int v) {
row = r;
col = c;
val = v;
}
};
struct InfoComparator {
bool operator() (const Info& o1, const Info& o2) {
if (o1.col != o2.col) {
return o1.col & collects) {
if (root->left != nullptr) {
Info leftInfo(rootInfo.row + 1, rootInfo.col - 1, root->left->val);
collects.push_back(leftInfo);
dfs(root->left, leftInfo, collects);
}
if (root->right != nullptr) {
Info rightInfo(rootInfo.row + 1, rootInfo.col + 1, root->right->val);
collects.push_back(rightInfo);
dfs(root->right, rightInfo, collects);
}
}
vector> verticalTraversal(TreeNode* root) {
vector collects;
Info rootInfo(0, 0, root->val);
collects.push_back(rootInfo);
dfs(root, rootInfo, collects);
sort(collects.begin(), collects.end(), InfoComparator());
vector> ans;
for (int i = 0; i ());
}
ans.back().push_back(collects[i].val);
}
return ans;
}
int main() {
TreeNode* leaf7 = new TreeNode(7);
TreeNode* leaf15 = new TreeNode(15);
TreeNode* leaf20 = new TreeNode(20, leaf15, leaf7);
TreeNode* leaf9 = new TreeNode(9);
TreeNode* root = new TreeNode(3, leaf9, leaf20);
vector> result = verticalTraversal(root);
for (int i = 0; i 
服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net
机房租用，北京机房租用，IDC机房托管， http://www.fwqtg.net
TCP（Transmission Control Protocol，传输控制协议）的历史可以追溯到1970年代初期，最初的版本是RFC 793，后来经过多次更新和改进，包括RFC 1122、RFC 1323、RFC 2018、RFC 2581、RFC 2873…
