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完整代码如下：

packagemainimport("fmt""sort")typeTreeNodestruct{ValintLeft*TreeNodeRight*TreeNode}typeInfostruct{rowintcolintvalint}funcNewInfo(r,c,vint)Info{returnInfo{row:r,col:c,val:v}}typeByColThenRowThenVal[]Infofunc(bcByColThenRowThenVal)Len()int{returnlen(bc)}func(bcByColThenRowThenVal)Less(iint,jint)bool{ifbc[i].col!=bc[j].col{returnbc[i].col}ifbc[i].row!=bc[j].row{returnbc[i].row}returnbc[i].val}func(bcByColThenRowThenVal)Swap(iint,jint){bc[i],bc[j]=bc[j],bc[i]}funcverticalTraversal(root*TreeNode)[][]int{collects:=make([]Info,0,1000)rootInfo:=NewInfo(0,0,root.Val)collects=append(collects,rootInfo)dfs(root,rootInfo,&collects)sort.Sort(ByColThenRowThenVal(collects))ans:=make([][]int,0,1000)fori:=0;iifi==0||collects[i-1].col!=collects[i].col{ans=append(ans,[]int{})}ans[len(ans)-1]=append(ans[len(ans)-1],collects[i].val)}returnans}funcdfs(root*TreeNode,rootInfoInfo,collects*[]Info){ifroot.Left!=nil{leftInfo:=NewInfo(rootInfo.row+1,rootInfo.col-1,root.Left.Val)*collects=append(*collects,leftInfo)dfs(root.Left,leftInfo,collects)}ifroot.Right!=nil{rightInfo:=NewInfo(rootInfo.row+1,rootInfo.col+1,root.Right.Val)*collects=append(*collects,rightInfo)dfs(root.Right,rightInfo,collects)}}funcmain(){leaf7:=&TreeNode{7,nil,nil}leaf15:=&TreeNode{15,nil,nil}leaf20:=&TreeNode{20,leaf15,leaf7}leaf9:=&TreeNode{9,nil,nil}root:=&TreeNode{3,leaf9,leaf20}result:=verticalTraversal(root)fmt.Println(result)}

c++完整代码如下：

#include#include#includeusingnamespacestd;structTreeNode{intval;TreeNode*left;TreeNode*right;TreeNode():val(0),left(nullptr),right(nullptr){}TreeNode(intx):val(x),left(nullptr),right(nullptr){}TreeNode(intx,TreeNode*left,TreeNode*right):val(x),left(left),right(right){}};structInfo{introw;intcol;intval;Info(intr,intc,intv){row=r;col=c;val=v;}};structInfoComparator{booloperator()(constInfo&o1,constInfo&o2){if(o1.col!=o2.col){returno1.col}if(o1.row!=o2.row){returno1.row}returno1.val}};voiddfs(TreeNode*root,InforootInfo,vector&collects){if(root->left!=nullptr){InfoleftInfo(rootInfo.row+1,rootInfo.col-1,root->left->val);collects.push_back(leftInfo);dfs(root->left,leftInfo,collects);}if(root->right!=nullptr){InforightInfo(rootInfo.row+1,rootInfo.col+1,root->right->val);collects.push_back(rightInfo);dfs(root->right,rightInfo,collects);}}vector>verticalTraversal(TreeNode*root){vectorcollects;InforootInfo(0,0,root->val);collects.push_back(rootInfo);dfs(root,rootInfo,collects);sort(collects.begin(),collects.end(),InfoComparator());vector>ans;for(inti=0;iif(i==0||collects[i-1].col!=collects[i].col){ans.push_back(vector());}ans.back().push_back(collects[i].val);}returnans;}intmain(){TreeNode*leaf7=newTreeNode(7);TreeNode*leaf15=newTreeNode(15);TreeNode*leaf20=newTreeNode(20,leaf15,leaf7);TreeNode*leaf9=newTreeNode(9);TreeNode*root=newTreeNode(3,leaf9,leaf20);vector>result=verticalTraversal(root);for(inti=0;ifor(intj=0;jcout<}cout<}return0;}