минимальная высота двоичного дерева?

Question

Я задаю этот вопрос после прочтения ниже сообщение:

How to find minimum possible height of tree?

На самом деле я хочу, чтобы мой алгоритм для возврата 4, если вход дано бинарное дерево выглядит следующим образом: 100, 50, 70, 60.

, но приведенный ниже код возвращает только 1, потому что он не различает лист [left == NULL & & right == NULL] и узел с одним ребенком.

int minDepth(TreeNode root) { 
    if (root == null) { 
     return 0; 
    } 
    return 1 + Math.min(minDepth(root.left), minDepth(root.right)); 
} 

Никто не объяснил, что мы должны делать, если мы хотим, чтобы на выходе как 4 вместо 1.

Может кто-нибудь пожалуйста, покажите мне код, который возвращает 4 вместо 1?

Я думаю, что я выбрал неправильные значения образцов выше, и люди смущаются о том, что я на самом деле ищу! Итак, переформатирование моих вопросов ниже:

Предположим, что любой узел может иметь 0,1 или 2 детей. Пожалуйста, рассмотрите этот пример ввода - 100, 50, 150, 30, 70, 200, 20, 40, 60, 80, 10. Теперь я хочу, чтобы моя функция вернула высоту как 3 [100-> 150-> 200]. Я называю эту ветвь [100-> 150-> 200] минимальной высотой дерева. Может быть, я неправильно в аналогии с минимальной высоты, но все, что я хочу, чтобы вернуться 3.

Дерево выглядит так -

     100 
        / \\ 
        /  \\ 
        50   150 
       / \   \\ 
       30  70   200 
      /\ /\ 
      20 40 60 80 
     /
      10 

И мне нужно, чтобы выяснить, кратчайшее расстояние между корневой узел и листовой узел [100-> 150-> 200] = 3.

Это мой код -

struct node 
{ 
    struct node* left; 
    int data; 
    struct node* right; 
}; 

void add(struct node** root, int data) 
{ 
    if(*root == NULL) 
    { 
     (*root) = (struct node*)malloc(sizeof(node)); 
     (*root)->left = NULL; 
     (*root)->right = NULL; 
     (*root)->data = data; 
    } 
    else 
    { 
     if(data < (*root)->data) 
      add(&(*root)->left, data); 
     else 
      add(&(*root)->right, data); 
    } 

} 

void inorder(struct node* root) 
{ 
    if(root == NULL) 
     return; 
    inorder(root->left); 
    cout<<root->data<<" "; 
    inorder(root->right); 
} 

int minDepth(struct node* root) 
{ 
    if (root == NULL) 
    { 
     return 0; 
    } 
    return 1 + min(minDepth(root->left), minDepth(root->right)); 
} 

int main() 
{ 
     struct node* root = NULL; 
     add(&root, 100); 
     add(&root, 50); 
     add(&root, 150); 
     add(&root, 30); 
     add(&root, 70); 
     add(&root, 200); 
     add(&root, 20); 
     add(&root, 40); 
     add(&root, 60); 
     add(&root, 80); 
     add(&root, 10); 
     inorder(root); 
     cout<<endl; 
     int i = minDepth(root); 
     cout<<i<<endl; // this should be 3 
     getchar(); 
     return 0; 
} 

Answer 1

Мне кажется, что вы хотите знать размер дерева, а не его высота.

Итак, вместо того, чтобы выбрать наименьшую высоту двух поддеревьев под вашим корнем (функция minDepth), вы хотите суммировать их размеры.

Следующая функция добавляет один к размеру каждого из левого и правого поддеревьев, если узел не является нулевым (на самом деле он не был бы узлом и не должен учитываться).

int sizeOfTree(TreeNode root){ 
    if (root == nulll) {return 0;} 
     return 1 + sizeOfTree(root.left) + sizeOfTree(root.right); 
} 

Рекурсивно это найдет количество узлов в вашем дереве (также известном как его размер).

EDIT: После того, как вопрос был рассмотрен, я думаю, что это то, что вы хотите:

int shortestBranch(TreeNode root){ 
    if (root == null) {return 0;} 
    if (root.left == null && root.right == null){ 
     return 1; 
    } else if (root.left == null) { 
     return 1 + shortestBranch(root.right); 
    } else if (root.right == null) { 
     return 1 + shortestBranch(root.left); 
    } else { 
     return 1 + Math.min(shortestBranch(root.right), shortestBranch(root.left)); 
    } 
} 

Answer 2

int minDepth(TreeNode root) 
{ 
    if(root == null) 
     return 0; 
    if(root.left == null && root.right == null) 
     return 1; 
    int l = minDepth(root.left); 
    int r = minDepth(root.right); 
    if(l == 0) 
     return r; 
    if(r == 0) 
     return l; 
    return 1 + Math.min(l,r); 
}