二叉树垂直视图遍历代码触发段错误的原因咨询
段错误触发原因定位
- 递归逻辑致命错误:
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
相关产品推荐
相关产品推荐

