问二叉树的最小深度:递归程序总是返回0

EN

代码中存在以下问题：

• minHeight被初始化为0，因此它永远不会得到更大的值。这意味着无论您的代码得到什么输入，它都将始终返回0。minHeight应该设置为一个非常大的值，比如INT_MAX，这样任何叶子的深度都会比初始值小。
• 当空树作为输入时，代码具有未定义的行为。应该检查那个边界情况。
• currHeight并不总是在它应该减少的时候减少。无论if ...else if ... else if ...结构中的情况如何-- currHeight应该减少。对于这两个中间的情况，没有这样做。更好的做法是在一个共同的地方，在函数体的末尾执行这个currHeight--。

下面是包含这些更正的代码：

    int minHeight = INT_MAX, // Set at an extreme high value
        currHeight = 0;

    int minDepth(TreeNode* root) {
        if (root != nullptr) return 0; // boundary case: empty tree
        searchTree(root);
        return minHeight;
    }

    void searchTree(TreeNode* p) {
        currHeight++;
        if (p->right == nullptr && p->left == nullptr) 
        {
            // Don't increase currHeight here, but at a common spot in the code
            if (currHeight < minHeight) minHeight = currHeight;
        }
        else if (p->right == nullptr)
            searchTree(p->left);
        else if (p->left == nullptr)
            searchTree(p->right);
        else
        {
            searchTree(p->left);
            searchTree(p->right);
        }
        currHeight--; // Always do this

    }

请注意，这不是解决问题的最有效方法。该算法将访问所有节点，而宽度优先遍历可以在找到叶子后立即停止。

下面是一个使用广度优先遍历的扰流解决方案：

`int minDepth(TreeNode* root) { if (root == nullptr) return 0; vector<TreeNode*> level, nextLevel; level.push_back(root); for (int depth = 1; true; depth++) { nextLevel.clear(); for (auto node : level) { if (node->left == nullptr && node->right == nullptr) return depth; // found the first leaf: solved! if (node->left != nullptr) nextLevel.push_back(node->left); if (node->right != nullptr) nextLevel.push_back(node->right); } level = nextLevel; // copy } }`