算法题:二叉树的垂序遍历
描述
给你二叉树的根结点 root ,请你设计算法计算二叉树的 垂序遍历 序列。
对位于 (row, col) 的每个结点而言,其左右子结点分别位于 (row 1, col - 1) 和 (row 1, col 1) 。树的根结点位于 (0, 0) 。
二叉树的 垂序遍历 从最左边的列开始直到最右边的列结束,按列索引每一列上的所有结点,形成一个按出现位置从上到下排序的有序列表。如果同行同列上有多个结点,则按结点的值从小到大进行排序。
返回二叉树的 垂序遍历 序列。
示例 1:
输入:root = [3,9,20,null,null,15,7]
输出:[[9],[3,15],[20],[7]]
解释:
列 -1 :只有结点 9 在此列中。
列 0 :只有结点 3 和 15 在此列中,按从上到下顺序。
列 1 :只有结点 20 在此列中。
列 2 :只有结点 7 在此列中。
示例 2:
输入:root = [1,2,3,4,5,6,7]
输出:[[4],[2],[1,5,6],[3],[7]]
解释:
列 -2 :只有结点 4 在此列中。
列 -1 :只有结点 2 在此列中。
列 0 :结点 1 、5 和 6 都在此列中。
1 在上面,所以它出现在前面。
5 和 6 位置都是 (2, 0) ,所以按值从小到大排序,5 在 6 的前面。
列 1 :只有结点 3 在此列中。
列 2 :只有结点 7 在此列中。
示例 3:
输入:root = [1,2,3,4,6,5,7]
输出:[[4],[2],[1,5,6],[3],[7]]
解释:
这个示例实际上与示例 2 完全相同,只是结点 5 和 6 在树中的位置发生了交换。
因为 5 和 6 的位置仍然相同,所以答案保持不变,仍然按值从小到大排序。
提示:
树中结点数目总数在范围 [1, 1000] 内
0 <= Node.val <= 1000
链接:https://leetcode-cn.com/problems/vertical-order-traversal-of-a-binary-tree
思路
先遍历树找出输出数组的长度,再次遍历树并保存每个节点的深度和值,将节点插入对应横坐标的列表,最后再排序
代码
class Solution {public: int m_left, m_right; vector<vector<int>> verticalTraversal(TreeNode* root) { getRange(root, 0); vector<vector<pair<int, int>>> res(m_right-m_left 1, vector<pair<int, int>>()); dfs(root, res, -m_left, 0); for (auto& list : res) { sort(list.begin(), list.end(), [](pair<int, int>& a, pair<int, int>& b) -> bool { if (a.first > b.first) return false; else if (a.first < b.first) return true; return a.second < b.second; }); } vector<vector<int>> ans; for (auto & list : res) { vector<int> temp; for (auto& p : list) { temp.push_back(p.second); } ans.push_back(temp); } return ans; } void dfs(TreeNode* root, vector<vector<pair<int, int>>>& res, int i, int depth) { if (root) { res[i].push_back({depth, root->val}); } if (root->left) dfs(root->left, res, i - 1, depth 1); if (root->right) dfs(root->right, res, i 1, depth 1); } void getRange(TreeNode* root, int index) { if (!root) return; if (m_left > index) m_left = index; if (m_right < index) m_right = index; if (root->left) getRange(root->left, index-1); if (root->right) getRange(root->right, index 1); }};
复杂度
n 表示节点个数
时间复杂度:O(n)
空间复杂度:O(n)