二叉樹中的中間節點

Question

我對以下問題進行了考試，我無法回答：我們有一個二叉樹，其中每個節點都有一定的高度（從底部）和一定深度（從根部）。我們從零開始計數;例如：對於具有單個孩子的根的樹，孩子的深度將是1，並且高度將是0.

找到一個遞歸算法，該算法打印所有中值節點，即當節點的高度等於其深度。

一個提示被給予這是：給d（深度）作爲函數的自變量和高度作爲返回值...

Answer 1

Python實現，其中節點是具有屬性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的高度）。