二叉树的最小深度

题目

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

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

思想1：

使用后序遍历，判断左右子树的高度，但是需要注意的是，若某节点只有一个子树，那么直接返回该高度，因为题目说到最近叶子节点，我们需要找到拥有叶子节点的路径。

class Solution {
public:
    int GetHeight(TreeNode* node)
    {
        if(NULL == node){
            return 0;
        }
        int left_height = GetHeight(node->left);
        int right_height = GetHeight(node->right);
        if(NULL != node->left && NULL != node->right)  //节点拥有左右孩子，那么证明该节点拥有左右子树，可以直接返回最小值
        {
            return min(left_height, right_height) + 1;
        }
        return max(left_height, right_height) + 1;  //其他情况下返回拥有叶子节点的路径长度
    }
    int minDepth(TreeNode* root) {
        return GetHeight(root);
    }
};

思想2：

使用先序遍历，遍历每一条路径的每一个步骤，需要注意的是需要在叶子节点处添加判断。

class Solution {
public:
    int result;
    void GetDepth(TreeNode* node, int depth)
    {
        if(NULL == node->left && NULL == node->right)
        {
            if(0 == result)
            {
                result = depth;
            }
            else
            {
                result = result < depth ? result : depth;
            }
        }
        if(node->left)
        {
            depth++;
            GetDepth(node->left, depth);
            depth--;
        }
        if(node->right)
        {
            depth++;
            GetDepth(node->right, depth);
            depth--;
        }
    }
    int minDepth(TreeNode* root) {
        result = 0;
        if(NULL == root)
        {
            return result;
        }
        GetDepth(root, 1);
        return result;
    }
};

思想3：

同样可以使用层次遍历解决，但是需要判断队列中的节点是否为叶子节点，遇到第一个叶子节点即结束

class Solution {
public:

    int minDepth(TreeNode* root) {
        if (root == NULL) return 0;
        int depth = 0;
        queue<TreeNode*> que;
        que.push(root);
        while(!que.empty()) {
            int size = que.size();
            depth++; // 记录最小深度
            for (int i = 0; i < size; i++) {
                TreeNode* node = que.front();
                que.pop();
                if (node->left) que.push(node->left);
                if (node->right) que.push(node->right);
                if (!node->left && !node->right) { // 当左右孩子都为空的时候，说明是最低点的一层了，退出
                    return depth;
                }
            }
        }
        return depth;
    }
};