leetcode---987. 二叉树的垂序遍历-白红宇

leetcode---987. 二叉树的垂序遍历

阅读量：187 次

发布时间：2019-02-28

本文共 1625 字，大约阅读时间需要 5 分钟。

为了解决这个问题，我们需要实现一个二叉树的垂序遍历，并按特定规则返回结点值。垂序遍历是按照垂线移动的顺序，类似于从左下方到右下方的顺序。每个结点的位置由其X和Y坐标决定，遍历时，每当垂线碰到一个结点，就按Y坐标递减的顺序报告结点值。如果两个结点位置相同，首先报告的结点值较小。

方法思路

垂序遍历定义：垂序遍历是按照垂线从左到右移动的顺序进行的。每个结点的位置由其X和Y坐标决定，左子结点在(X-1, Y-1)，右子结点在(X+1, Y-1)。

遍历记录：使用深度优先搜索（DFS）遍历二叉树，记录每个结点的位置和值。

排序规则：将记录的结点按X坐标升序排列，如果X坐标相同，按Y坐标降序排列，如果Y坐标也相同，则按结点值升序排列。

结果生成：按X坐标分组，生成最终结果列表。

解决代码

#include 
   
    #include 
    
     using namespace std;struct node {    int x;    int y;    int val;};static bool cmp(node a, node b) {    if (a.x != b.x) {        return a.x < b.x;    } else if (a.y != b.y) {        return a.y > b.y;    } else {        return a.val < b.val;    }}void dfs(int x, int y, TreeNode* root) {    if (root == nullptr) return;    node t;    t.x = x;    t.y = y;    t.val = root->val;    vector
     
      & vn = ref;    vn.push_back(t);    if (root->left != nullptr) {        dfs(x-1, y-1, root->left);    }    if (root->right != nullptr) {        dfs(x+1, y-1, root->right);    }}vector
      
       
        > verticalTraversal(TreeNode* root) {    vector
        
          vn; dfs(0, 0, root); sort(vn.begin(), vn.end(), cmp); vector
         
          
           > res; if (vn.empty()) return res; int t = vn[0].x; vector
           
             tmp; tmp.push_back(vn[0].val); for (size_t i = 1; i < vn.size(); ++i) { if (vn[i].x == t) { tmp.push_back(vn[i].val); } else { res.push_back(tmp); tmp.clear(); t = vn[i].x; tmp.push_back(vn[i].val); } } res.push_back(tmp); return res;}