二叉树最小深度

题目

Given a binary tree, find its minimum depth.

The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.

求出一个二叉树的最小子叶路径。
**难度：**easy

思路：
对于所有关系二叉树（或者树）的题目，首先应该考虑的就是递归了。
如果知道一个节点左子树和右子树的最小深度，那么该节点的最小深度也就确定了。因此可以看出该题目只要递归的求出一个节点左右子树各自的深度即可。
要注意到达叶子节点才算一条合格的路径。

代码

 struct TreeNode {
     int val;
     TreeNode *left;
     TreeNode *right;
     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 };

class Solution {
public:
    int minDepth(TreeNode* root) {
        if (!root) {
            return 0;
        }
         */*如果是叶子节点则返回*/*
        if (root->left == nullptr && root->right == nullptr)
        {
            return 1;
        }
        int minleft = -1;
        int minright = -1;
        */* 如果存在左子树则计算左子树的最小深度*/*
        if (root->left) {
            minleft = minDepth(root->left);
        }
        */* 如果存在右子树则计算左子树的最小深度*/*
        if (root->right) {
            minright = minDepth(root->right);
        }
        */*返回该节点的最小深度，因为叶子节点不可能走到此处，所以只考虑二中情况*/*
        if (root->left == nullptr || root->right == nullptr) {
            return minleft < minright ? (minright + 1) : (minleft + 1);
        }
        else {
            return minleft > minright ? (minright + 1) : (minleft + 1);
        }
    }
};

accept后查看了别人的代码，真是精炼。

/* 参考答案*/
class Solution {
public:
    int minDepth(TreeNode* root) {
        if(root==NULL) return 0;
        if(root->left==NULL) return minDepth(root->right)+1;
        if(root->right==NULL) return minDepth(root->left)+1;
        return min(minDepth(root->left),minDepth(root->right))+1;
    }
};