recursion - 二叉树的中间节点

Question

我有一个我无法回答的问题的考试：我们有一个二叉树，其中每个节点都有一定的高度（从底部）和一定的深度（从根）。我们从零开始计数；例如：对于具有单个子节点的根树，子节点的深度为 1，高度为 0。

找到一个递归算法，它打印所有的中间节点，即当一个节点的高度等于它的深度时。

给出的提示是：将 d(depth) 作为函数的参数，将高度作为返回值...

Answer 1

Python 实现，其中 node 是具有属性的对象children。

def R(node, d):
  if not node.children: # No children, leaf node
    height = 0
  else:
    height = max( R(child, d+1) for child in node.children ) + 1
  if height == d:
    print node  # Or some node.id
  return height

R(root, 0)  # Call with a root node

Answer 2

void medianInTree(class tree* root, int depth, int height)
{

    if(root)
    {
         if(height == depth)
             cout<<"   "<<root->data;
         medianInTree(root->left, depth-1, height+1);
         medianInTree(root->right, depth-1, height+1);
    }
}

将深度作为树的高度（考虑根的高度=1）。