104 二叉树的垂序遍历

问题描述：给你二叉树的根节点root，请你设计算法计算二叉树的垂序遍历序列。对位于(row,col)的每个节点而言，其左右子节点分别为(row+1,col-1)和(row+1,col+1),根节点位于(0,0),二叉树的垂序遍历是从最左边的列开始直到最右边的列结束，按列索引每一列上的所有节点，形成一个按出现位置从上到下排序的有序列表。如果同行同列上有多个节点，则按照节点的值从小到大进行排序。

思路：本例思路在于先通过遍历的方式将所有节点进行保存于List中，然后根据列、行、数值的方法进行排序，排序后将结果放入最后的结果List中。

public void dfs(TreeNode root,int row,int col,List<int[]arr>list)
{
if(root==null){return;}
list.add(new int[]{row,col,root.val});
dfs(root.left,row+1,col-1,list);
dfs(root.right,row+1,col+1,list);
}
public List<List<Integer>>Dfs(TreeNode root)
{
List<int[]arr>list=new List<>();
dfs(root,0,0,list);
Collection.sort(list,(arr1,arr2)->{
if(arr1[2]!=arr2[2]){return arr1[2]-arr2[2];}
if(arr1[1]!=arr2[1]){return arr1[1]-arr1[1];}
return arr1[0]-arr2[0];
});
List<List<Integer>>res=new List<>();
res.add(new List<Integer>(list.get(0)[2]));
int colIndex=0;
for(int i=1;i<list.size();i++)
{
if(colIndex!=list.get(i)[1])
{
res.add(new List<Integer>(list.get(i)[2]));
conIndex=list.get(i)[1];
}
res.get(conIndex).add(list.get(i)[0]);
}
???????return res;
}