이진 트리의 최소 높이?

Question

나는 아래의 글을 읽은 후에이 질문을하고있다 : 100, 50, 70, 60 :

How to find minimum possible height of tree?

이 사실 나는 다음과 같은 이진 트리에 주어진 입력되면 내 알고리즘은 4를 반환합니다.

그러나 아래 코드는 리프 [왼쪽 == NULL & & 오른쪽 == NULL]과 단 하나의 자식이있는 노드를 구분하지 않기 때문에 1 만 반환합니다. 우리는 누군가가 나에게 4 대신 1 반환 코드를 보여 주시겠습니까 4 대신 1

로 출력을 원하는 경우

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

아무도

우리가 무엇을해야 설명했다?

위의 잘못된 샘플 값을 선택했는데 사람들이 실제로 무엇을 찾고 있는지 혼란스러워하고 있습니다 !! 그래서, 내 질문을 다시 골라 내면 :

어떤 노드라도 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 함수) 아래에있는 두 하위 트리의 가장 작은 높이를 선택하여 크기를 합산하는 대신.

다음 함수는 노드가 null이 아닌 경우 (실제 노드가 아니며 계산되지 않아야 함) 각 왼쪽 및 오른쪽 하위 트리의 크기에 1을 더합니다.

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

재귀 적으로 트리의 노드 수 (크기라고도 함)를 찾습니다.

편집 :

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); 
}