算法题：二叉树的垂序遍历

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了算法题：二叉树的垂序遍历，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2540字，纯文字阅读大概需要4分钟。

内容图文

描述

给你二叉树的根结点 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)

内容总结

以上是互联网集市为您收集整理的算法题：二叉树的垂序遍历全部内容，希望文章能够帮你解决算法题：二叉树的垂序遍历所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---