111. Minimum Depth of Binary Tree

缺乏、安全感 2022-05-04 10:28 159阅读 0赞

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.

**Note:** A leaf is a node with no children.

**Example:**

Given binary tree `[3,9,20,null,null,15,7]`,

3
       / \
      9  20
        /  \
       15   7

return its minimum depth = 2.

方法一：递归

/**
     * Definition for a binary tree node.
     * 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 == NULL)
                return 0;
            
            if(root->left != NULL && root->right!= NULL)
                return 1 + min(minDepth(root->left), minDepth(root->right));     
            else if(root->left==NULL)
                return 1 + minDepth(root->right);       
            else if(root->right== NULL)
                return 1 + minDepth(root->left);           
        }
    };

方法2：非递归

/**
     * Definition for a binary tree node.
     * 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 == NULL)
                return 0;
            
            queue<TreeNode*> node;
            node.push(root);
            int count=0;
            while(!node.empty())
            {
                count++;
                int len = node.size();
                for(int i=0;i<len;i++)
                {
                    root = node.front();
                    node.pop();
                    if(root->left == NULL && root->right == NULL)
                        return count; 
                    if(root->left)
                        node.push(root->left);
                    if(root->right)
                        node.push(root->right);
                }           
            }    
            return count;
        }
    };