111. 二叉树的最小深度(递归法)

111. 二叉树的最小深度

题解

思路：该题看似与104. 二叉树的最大深度(递归法) 差不多，但其实相差得还是有点多。在解该题的时候对于“确认单层递归的逻辑”上，我先是将104. 二叉树的最大深度(递归法) 中对应的代码改成了：

int leftDepth = getDepth(node->left);
int rightDepth = getDepth(node->right);
int result = 1 + min(leftDepth, rightDepth);//!!!!!
return result;

调试时发现自己进入了一个误区，比如，下图中树的最小深度是3。如果按照上面的求法，没有左孩子的分支会算为最小深度，即为0。注意题目：最小深度是最近叶子节点到根节点的节点个数。

因此，如果左子树为空，右子树不为空，则最小深度是右子树的最小深度+1；反之，如果左子树不为空，右子树为空，则最小深度是左子树的最小深度+1。

代码(C++)：

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode* next;
    TreeNode(int value) : val(value), left(nullptr), right(nullptr), next(nullptr) {}
};

//递归法，后序遍历(左右中)
//(1.确定递归函数的参数和返回值；2.确定终止条件；3.确定单层递归的逻辑)
class Solution2 {
public:
    int minDepth(TreeNode* root) {
        if (root == nullptr) return 0;
        int leftLevel = minDepth(root->left);
        int rightLevel = minDepth(root->right);

        int depth = 0;
        if (root->left == nullptr && root->right != nullptr) {
            depth = rightLevel + 1;
        } else if (root->left != nullptr && root->right == nullptr) {
            depth = leftLevel + 1;
        } else {
            depth = min(leftLevel, rightLevel) + 1;
        }
        return depth;
    }
};

//递归法，后序遍历(左右中)
//(1.确定递归函数的参数和返回值；2.确定终止条件；3.确定单层递归的逻辑)
class Solution3 {
public:
    int getDepth(TreeNode* node) {
        if (node->left == nullptr && node->right == nullptr) return 1;
        int leftLevel = 0;
        int rightLevel = 0;
        if (node->left) leftLevel = getDepth(node->left);
        if (node->right) rightLevel = getDepth(node->right);

        int depth = 0;
        if (node->left == nullptr && node->right != nullptr) {
            depth = rightLevel + 1;
        } else if (node->left != nullptr && node->right == nullptr) {
            depth = leftLevel + 1;
        } else {
            depth = min(leftLevel, rightLevel) + 1;
        }
        return depth;
    }
    int minDepth(TreeNode* root) {
        if (root == nullptr) return 0;
        int result = getDepth(root);
        return result;
    }
};

代码(JavaScript)：

//构造函数
function TreeNode(val, left, right) {
    this.val = (val === undefined ? 0 : val),
        this.left = (left === undefined ? null : left),
        this.right = (right === undefined ? null : right)
}

var root = new TreeNode();

//递归法
var minDepth = function(root) {
    if (root === null) return 0;
    var leftLevel = minDepth(root.left);
    var rightLevel = minDepth(root.right);
    var depth = 0;
    if (root.left === null && root.right != null) depth = rightLevel + 1;
    else if (root.left != null && root.right === null) depth = leftLevel + 1;
    else depth = Math.min(leftLevel, rightLevel) + 1;
    return depth;
};

//这里用JS把之前C++写的迭代法(队列)写一下
var minDepth1 = function(root) {
    var que = new Array();
    if (root != null) que.push(root);
    var depth = 1;
    while (que.length != 0) {
        var size = que.length;
        // 以下 for 循环中的 size 不能直接用 que.length, 因为 que.length 会改变
        for (var i = 0; i < size; i++) {
            var node = que.shift();
            if (node.left === null && node.right === null) return depth;
            if (node.left != null) que.push(node.left);
            if (node.right != null) que.push(node.right);
        }
        depth++;
    }
    return depth - 1;
}

分析：

时间复杂度：O(N)
空间复杂度：O(N)