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 < bc[j].col } if bc[i].row != bc[j].row { return bc[i].row < bc[j].row } return bc[i].val < bc[j].val}
func (bc ByColThenRowThenVal) Swap(i int, j int) { bc[i], bc[j] = bc[j], bc[i] }
func verticalTraversal(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) for i := 0; i < len(collects); i++ { if i == 0 || collects[i-1].col != collects[i].col { ans = append(ans, []int{}) } ans[len(ans)-1] = append(ans[len(ans)-1], collects[i].val) } return ans}
func dfs(root *TreeNode, rootInfo Info, collects *[]Info) { if root.Left != nil { leftInfo := NewInfo(rootInfo.row+1, rootInfo.col-1, root.Left.Val) *collects = append(*collects, leftInfo) dfs(root.Left, leftInfo, collects) } if root.Right != nil { rightInfo := NewInfo(rootInfo.row+1, rootInfo.col+1, root.Right.Val) *collects = append(*collects, rightInfo) dfs(root.Right, rightInfo, collects) }}
func main() { 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 <iostream>#include <vector>#include <algorithm>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 < o2.col; } if (o1.row != o2.row) { return o1.row < o2.row; } return o1.val < o2.val; }};
void dfs(TreeNode* root, Info rootInfo, vector<Info>& 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<vector<int>> verticalTraversal(TreeNode* root) { vector<Info> collects; Info rootInfo(0, 0, root->val); collects.push_back(rootInfo); dfs(root, rootInfo, collects); sort(collects.begin(), collects.end(), InfoComparator()); vector<vector<int>> ans; for (int i = 0; i < collects.size(); i++) { if (i == 0 || collects[i - 1].col != collects[i].col) { ans.push_back(vector<int>()); } 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<vector<int>> result = verticalTraversal(root); for (int i = 0; i < result.size(); i++) { for (int j = 0; j < result[i].size(); j++) { cout << result[i][j] << " "; } cout << endl; } return 0;}
复制代码
评论