二叉树的最小高度？

Question

我在阅读下面的帖子后提出这个问题：

如何找到树的最小可能高度？

实际上，如果给二叉树的输入如下：100，50，70，60，我希望我的算法返回4。

但是下面的代码只返回1，因为它不区分叶[left==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-

这棵树看起来像这样-

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

我需要找出根节点和叶节点之间的最短距离[100-

这是我的密码-

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

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

Answer 2

在我看来，你想知道树的大小，而不是它的高度。

因此，与其选择根下两个子树的最小高度（minDepth函数），不如求其大小之和。

如果节点不为null（实际上根本不是节点，也不应计算），则以下函数将左、右子树的大小加一。

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