搜索+哈希/平衡树，LeetCode 987. 二叉树的垂序遍历

目录

一、题目

1、题目描述

2、接口描述

3、原题链接

二、解题报告

1、思路分析

2、复杂度

3、代码详解

一、题目

1、题目描述

给你二叉树的根结点 root ，请你设计算法计算二叉树的 垂序遍历 序列。

对位于 (row, col) 的每个结点而言，其左右子结点分别位于 (row + 1, col - 1) 和 (row + 1, col + 1) 。树的根结点位于 (0, 0) 。

二叉树的 垂序遍历 从最左边的列开始直到最右边的列结束，按列索引每一列上的所有结点，形成一个按出现位置从上到下排序的有序列表。如果同行同列上有多个结点，则按结点的值从小到大进行排序。

返回二叉树的 垂序遍历 序列。

2、接口描述

​

/**
 * Definition for a binary tree node.
 * 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) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> verticalTraversal(TreeNode* root) {

    }
};

3、原题链接

987. 二叉树的垂序遍历

二、解题报告

1、思路分析

我们由父节点的坐标可以推出左右孩子的坐标，那么我们可以从根节点进行广搜或者深搜，推出所有节点的坐标，然后对每一列按照行坐标和节点值进行排序，记录返回值即可

思路很简单，就是一模拟题，代码或许还可以写的更优雅。

2、复杂度

时间复杂度： O(nlogn)空间复杂度：O(n)

3、代码详解

​

/**
 * Definition for a binary tree node.
 * 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) {}
 * };
 */
class Solution {
public:
#define mkp make_pair
typedef TreeNode Node;
typedef pair<int,int> PII;
map<int, vector<PII>> mp;
set<int> cols;

    vector<vector<int>> verticalTraversal(TreeNode* root) {
        if(!root) return {};
        mp.clear(), cols.clear();
        function<void(Node*, const PII&)> dfs = [&](Node* x, const PII& p){
            mp[p.second].emplace_back(mkp(p.first, x->val));
            cols.insert(p.second);
            if(x->left) dfs(x->left, mkp(p.first+1, p.second-1));
            if(x->right) dfs(x->right, mkp(p.first+1, p.second+1));
        };
        dfs(root, mkp(0, 0));
        vector<vector<int>> ret(cols.size());
        int tot = 0;
        for(auto x : cols){
            sort(mp[x].begin(), mp[x].end());
            for(auto& p : mp[x])
                ret[tot].emplace_back(p.second);
            tot++;
        }
        return ret;
    }
};