111. 二叉树的最小深度

二叉树的最小深度

原题：

给定一个二叉树，找出其最小深度。

最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

说明：叶子节点是指没有子节点的节点。

示例 1：

输入：root = [3,9,20,null,null,15,7]
输出：2

示例 2：

输入：root = [2,null,3,null,4,null,5,null,6]
输出：5

提示：

• 树中节点数的范围在 [0, 105] 内
• -1000 <= Node.val <= 1000

解题方法：

解法一（使用层次遍历）：

class Solution {
public:
    int minDepth(TreeNode* root) {
        if(!root) return 0;
        int minDepth=1;
        queue<TreeNode*> que;
        que.push(root);
        while(!que.empty())
        {
            int size=que.size();
            for(int i=0;i<size;i++)
            {
                TreeNode* node=que.front();
                que.pop();
                if(!node->left&&!node->right)
                {
                    return minDepth;
                }
                if(node->left) que.push(node->left);
                if(node->right) que.push(node->right);
            }
            minDepth++;
        }
        return minDepth;
    }


};

解法二（使用递归）：

class Solution {
public:
    int minDepth(TreeNode* root) {
        if(!root) return 0;
        int minDepth=INT_MAX;
        int curdepth=1;
        MinDepth(root,minDepth,curdepth);
        return minDepth;
    }

    void MinDepth(TreeNode* root,int& minDepth,int curdepth)
    {
        if(!root) return;
        if(!root->left&&!root->right)
        {
            minDepth=min(minDepth,curdepth);
        }
        curdepth++;
        MinDepth(root->left,minDepth,curdepth);
        MinDepth(root->right,minDepth,curdepth);
    }
};

解法三（递归的精简思路）：

class Solution {
public:
    int getDepth(TreeNode* node) {
        if (node == NULL) return 0;
        int leftDepth = getDepth(node->left);    // 左
        int rightDepth = getDepth(node->right);  // 右
                                                 // 中
        // 当一个左子树为空，右不为空，这时并不是最低点
        if (node->left == NULL && node->right != NULL) { 
            return 1 + rightDepth;
        }   
        // 当一个右子树为空，左不为空，这时并不是最低点
        if (node->left != NULL && node->right == NULL) { 
            return 1 + leftDepth;
        }
        int result = 1 + min(leftDepth, rightDepth); 
        return result;
    }

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

做题小结：

针对解法二：

1. 最重要的还是记住curdepth作为每个节点的属性，应该随着函数一起进行递归，才能保证其对应关系。

针对解法三：

1. 核心思想为：如果左子树为空，右子树不为空，说明最小深度是 1 + 右子树的深度。
   反之，右子树为空，左子树不为空，最小深度是 1 + 左子树的深度。最后如果左右子树都不为空，返回左右子树深度最小值 + 1 。