二叉树中节点的深度-Java 学习之路

-1

我编写了以下函数，它返回二叉树特定节点的深度 . 考虑这里的树：如果我要求节点5的深度，我应该从路径1 - > 2 - > 5得到3的答案 .

它不起作用;我得到0，即使我从函数返回高度 .

这里“data”是要找到其深度的值，root是树的根节点 . height的初始值为1（根节点为1级） .

int height_target(node *root,int data,int height){   if(root==NULL) return 0;

if(root->info==data)
return height;

height_target(root->left,data,height+1);
height_target(root->right,data,height+1);
}

6 回答

0

我认为你得到0作为回答，因为如果没有't a node with value equal to data. If you get 0 as a response it would be that the 2677764 you search in the binary tree there isn' t，条件 if(root->info==data) 永远不会满足 .

回复于 2024-05-05T07:46:56+08:00
0
你没有对从height_target返回的值做任何事情 .

大概你想要的东西：
```
return std::max(height_target(root->left,data,height+1),
                height_target(root->right,data,height+1));
```
回复于 2024-05-05T07:46:56+08:00
1
最值得注意的是，您的递归分支什么都不返回 . 将高度向后移动一级是不够的：你必须将它一直传递到线上 .

您需要捕获并返回左右子树调用的最大值 .

编辑：删除最后一句话......

因此，您需要从任何调用（向左或向右）找到所需节点的值返回值 . 你没有退货 . 就像是：
```
ldepth = height_target(root->left , data, height+1);
 if (ldepth > 0)
     return ldepth;
 rdepth = height_target(root->right, data, height+1);
 if (rdepth > 0)
     return rdepth;
 return 0;
```
这将返回找到所需节点的成功分支，失败时返回0 .
回复于 2024-05-05T07:46:56+08:00

好 . 我想我明白了 . 尝试使用这样的函数：

void height_target(node* root,int data,int height,int& h)
{
  if(root==NULL)
   return;

  if(root->info==data)
   h=height;

  height(root->left,data,height+1,h);
  height(root->right,data,height+1,h);

}

我想你假设树中不能有两个相等的值

回复于 2024-05-05T07:46:56+08:00

它不起作用;

这是对您的代码的一种可能的修复:(更新 - 此代码现在编译）

总结 - 代码的最后两行在'decursion'期间（当递归解析时）丢弃结果 .

int height_target(node* current, int data, int height)
{
   int retVal = 0;

   do {

      if (nullptr == current)
         break;   // 0 indicates not found

      if (current->info == data) { retVal = height;  break; }
      // found the node at 'height'; now de-curse

      retVal = height_target (current->left, data, height+1);
      if (retVal) break; // found data in left branch

      retVal = height_target(current->right, data, height+1);
      if(retVal) break;  // found data in right branch

   }while(0);

   return retVal;
}

想象一下，你的搜索项找到5层'up'，这样最高的递归返回5 .

在第4层，找不到数据，因此您的代码会搜索左侧分支和右侧分支 .

对于任一分支，当您的代码返回（从第5层），值为“5”时，您的代码将丢弃结果 .

在这个可能的解决方案中，我从左或右返回后测试了retVal . 现在，如果返回值（来自第5层）不为零，则函数将返回非零值;最终将堆栈中的值从“向下”返回到递归的底部 .

也许简化的调用跟踪可以说明：

height_target (., ., 1);   // first call, data not found at root
 |  height_target (., ., 2);   // recursive call, data not found
 |  |  height_target (., ., 3);   // recurse, not found
 |  |  |  height_target (., ., 4);   // recurse, not found
 |  |  |  |  height_target (., data, 5);   // found! 'decursion' begins
 |  |  |  |  |
 |  |  |  |  returns 5  // height 5 returns 5
 |  |  |  returns 5   // height 4 return 5
 |  |  returns 5   // height 3 returns 5
 |  returns 5   // height 2 returns 5
 returns 5    // height 1 returns 5

第一个电话现在返回5 .

回复于 2024-05-05T07:46:56+08:00

问题在于你理解 return 的作用：它不会终止对当前函数的所有调用，它只会结束所述函数的当前迭代并将值传递回前一个堆栈帧 .

考虑：

#include <iostream>

int f(int args) {
    if (args == 3)
        return args;
    f(args + 1);
    std::cout << args << "\n";
}

int main() {
    f(0);
}

http://ideone.com/59Dl7X

您的编译器应该一直警告您函数不返回值 .

你想要的是这样的：

static const size_t NODE_NOT_FOUND = 0;

size_t height_target_impl(node *root, int data, size_t height)
{
    if (root == nullptr)
        return NODE_NOT_FOUND;

    if (root->info == data)
        return height;

    int branch_height = height_target_impl(root->left, data, height + 1);
    if (branch_height != NODE_NOT_FOUND)
        return branch_height;
    return height_target_impl(root->right, data, height + 1);
}

size_t height_target(node* root, int data)
{
    return height_target_impl(root, data, 1);
}

被称为：

int h = height_target(root, data);

如果未找到节点或基于1的高度，则返回值0，其中1表示在根节点中找到数据 .

回复于 2024-05-05T07:46:56+08:00

二叉树中节点的深度

6 回答

相关问题