设计一个算法求二叉树中值为x的结点所在的层次。
时间: 2024-04-29 13:24:34 浏览: 178
按层次遍历二叉树的算法
可以使用递归遍历整个二叉树,在遍历每个结点时,比较该结点的值是否等于x,若等于则返回该结点所在的层次,否则继续遍历其左右子树。具体实现可以参考以下代码:
```
int findNodeLevel(TreeNode* root, int x, int level) {
if (root == nullptr) {
return 0;
}
if (root->val == x) {
return level;
}
int l = findNodeLevel(root->left, x, level + 1);
if (l != 0) {
return l;
}
return findNodeLevel(root->right, x, level + 1);
}
```
其中,参数root表示当前结点,x表示目标结点值,level表示当前结点的层次。递归的结束条件是当前结点为nullptr,即遍历到了叶子结点但仍然没找到目标结点,此时返回0表示未找到。若当前结点的值与目标结点值相等,直接返回当前层次level。否则继续遍历其左右子树,并将层次level加1传递给下一层递归。若左子树中找到目标结点,则返回左子树中的结果;否则返回右子树中的结果。
阅读全文