[Leetcode 111] Minimum Depth of Binary Tree

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.

Diffculty
Easy

Similar Problems
[LeetCode 102] Binary Tree Level Order Traversal Easy [LeetCode 104] Maximum Depth of Binary Tree Easy

Analysis

算法1: 直观的递归解法，分别求左右子树的最小深度，然后返回左右子树的最小深度中较小者 +1 算法2：层序遍历二叉树，找到最先遍历到的叶子的层数就是树的最小高度

Solutions

1、递归解法

class Solution {
public:
    int minDepth(TreeNode *root) {
        if(root == nullptr) return 0;
        int minleft = minDepth(root->left);
        int minright = minDepth(root->right);
        if(minleft == 0)
            return minright + 1;
        else if(minright == 0)
            return minleft + 1;
        else 
            return min(minleft, minright) + 1;
    }
};

2、非递归解法，层序遍历。

class Solution {
public:
    int minDepth(TreeNode *root) { // 层序遍历，碰到第一个叶子节点就停止，nullptr 作为每一层节点的分割标志
        if(root == nullptr) return 0;
        int res = 0;
        queue<TreeNode*> q;
        q.push(root);
        q.push(nullptr);
        while(!q.empty()){
            TreeNode *p = q.front();
            q.pop();
            if(p != nullptr){
                if(p->left) q.push(p->left);
                if(p->right) q.push(p->right);
                if(p->left == nullptr && p->right == nullptr){ // 左右子节点都是空，说明已经到了叶子节点。
                    res++;
                    break;
                }
            }
            else { // 下一层
                res++;
                if(!q.empty()) q.push(nullptr);
            }
        }
        return res;
    }
};