递归查找二叉树中节点的深度

Question

我坚持使用递归函数来查找二叉树中节点的深度，更具体地说，是在else条件中:

如果树是二叉搜索树，知道左子值总是低于父值，右子值总是高于父值，我可以添加一个If条件，这样如果节点x值低于根，我总是返回根-

当查看函数时，假设节点总是存在的，节点x永远不是根，并且在开始时传递的深度总是0。

int node_depth (Node x,Node root,int depth){
   if(x->parent==root){
       return depth;
   }
   else{
       return node_depth(x,root->leftchild,depth+1);
       return node_depth(x,root->rightchild,depth+1);
   }
}

如果树是二叉搜索：

else{
        if(x->value<root->value){
           return node_depth(x,root->leftchild,depth+1);
        }
        if(x->value>root->value){
           return node_depth(x,root->rightchild,depth+1);
        }
    }

Answer 1

您需要从根找到任何给定节点x的最大深度：

int node_depth(Node x, int depth){
    if (!x->parent) return depth;
    return node_depth(x->parent, depth + 1); 
}

你只要“向上”树，直到你发现父级不存在（意思是x是根，）