111. 二叉树的最小深度

Problem: 111. 二叉树的最小深度

思路

与上一道题目类似，都可以用后续遍历做，但是这里求最小深度，但是下面情况：

根节点的左节点为空右节点不为空，或者右节点为空左节点不为空

都不能算作最小深度为1  

所以我们要注意处理这种情况，放回的值应该是另一个字节的的最小深度

复杂度

时间复杂度:

添加时间复杂度, 示例： $O(n)$

空间复杂度:

添加空间复杂度, 示例： $O(n)$

Code

[]

/**

 * Definition for a binary tree node.

 * struct TreeNode {

 *     int val;

 *     TreeNode *left;

 *     TreeNode *right;

 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}

 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}

 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left),

 * right(right) {}

 * };

 */

class Solution {

public:

    int minDepth(TreeNode* root) { return foreach (root); }

    int foreach (TreeNode* node) {

        if (node == nullptr)

            return 0;

        int left = foreach (node->left);

        int right = foreach (node->right);

        if (node->left == nullptr && node->right != nullptr)

            return 1 + right;

        if (node->left != nullptr && node->right == nullptr)

            return 1 + left;

        return 1 + std::min(left, right);

    }

};