You need to enable JavaScript to run this app. 二叉树垂直视图遍历代码触发段错误的原因咨询
优惠活动
大模型
产品
解决方案
定价
更多

二叉树垂直视图遍历代码触发段错误的原因咨询

段错误触发原因定位
  • 递归逻辑致命错误:getvorder的两次递归调用均直接传入当前root指针,未传入root->left与root->right子节点。这导致递归永远无法命中root==NULL的终止条件,调用栈无限膨胀直至溢出,直接触发段错误。
  • 隐含栈溢出风险:即使修复传参问题,极端深度的斜二叉树(如全左/全右节点构成的数万级深度树)仍会因递归栈帧过多超出操作系统默认栈大小,再次触发栈溢出类段错误。
正确实现方案

修复后的递归版本

仅需补全递归调用的子节点参数,即可完成基础垂直遍历逻辑,同垂直线上的节点会按从上到下的顺序存储:

void getvorder(Node *root, map<int, vector<int>> &m, int hd)
{ 
    if(root == NULL)
        return;
    
    m[hd].push_back(root->data);
    
    // 修复点:传入对应左右子节点,而非当前root
    getvorder(root->left, m, hd - 1);
    getvorder(root->right, m, hd + 1);
}

vector<int> verticalOrder(Node *root)
{
    vector<int> v;
    map<int, vector<int>> m;
    if(root == NULL) 
        return v;
    getvorder(root, m, 0);
    
    for(auto &pair : m)
    {
        for(int val : pair.second)
        {
            v.push_back(val);
        }
    }
    return v;
}

BFS迭代版本(评测推荐)

针对极端深树的栈溢出问题,采用层序遍历替代递归,从根本上消除栈溢出风险,同时天然保证同垂直线上节点的顺序正确性:

vector<int> verticalOrder(Node *root)
{
    vector<int> v;
    if(root == NULL) 
        return v;
    
    map<int, vector<int>> m;
    // 队列存储节点与其对应的水平距离hd
    queue<pair<Node*, int>> q;
    q.push({root, 0});
    
    while(!q.empty())
    {
        auto curr = q.front();
        q.pop();
        Node *node = curr.first;
        int hd = curr.second;
        
        m[hd].push_back(node->data);
        
        // 入队非空的左右子节点,同步更新hd
        if(node->left)
            q.push({node->left, hd - 1});
        if(node->right)
            q.push({node->right, hd + 1});
    }
    
    // map默认按hd从小到大排序,直接遍历组装结果即可
    for(auto &pair : m)
    {
        for(int val : pair.second)
        {
            v.push_back(val);
        }
    }
    return v;
}

内容的提问来源于stack exchange,提问作者Bikramjit Das

相关产品推荐
方舟 Agent Plan

超全模态模型 × Harness 升级,最新支持 Deepseek-V4.1-Flash、GLM-5.3 系列、Doubao-Seedream-5.0-pro、Kimi-K3 (部分), 限时 9.9 元起

最近更新时间:2026.10.30 00:54:06