###### tags: `Leetcode` `easy` `tree` `python` `c++`

# 111. Minimum Depth of Binary Tree

## [題目來源: ] https://leetcode.com/problems/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.

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

Input: root = [2,null,3,null,4,null,5,null,6]
Output: 5

## 解題思路:
* 遞迴:
* 若沒左子->遞迴右子+1
* 若沒右子->遞迴左子+1
* min(遞迴左子,遞迴右子)+1
* bfs:
* queue存(root,1) 當前root,深度
* 終止條件:直到pop到某root沒有左右子

## Python:

class TreeNode(object):
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
    def insertLeft(self,node):
        if self.left==None:
            self.left=TreeNode(node)
        else:
            self.left.insertLeft(node)
    def insertRight(self,node):
        if self.right==None:
            self.right=TreeNode(node)
        else:
            self.right.insertRight(node)
    def printTree(self):
        root=self
        stack=[root]
        res=[]
        while stack:
            root=stack.pop(0)
            res.append(root.val)
            if root.left:
                stack.append(root.left)
            if root.right:
                stack.append(root.right)
        print(res)

class Solution(object):
    def minDepth(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        #bfs
        if not root:
            return 0
        que=[(root,1)]
        while que:
            cur,height=que.pop(0)
            if not cur.left and not cur.right:
                return height
            if cur.left:
                que.append((cur.left,height+1))
            if cur.right:
                que.append((cur.right,height+1))
        return -1

        '''
        dfs
        if not root:
            return 0
        if not root.left:
            return self.minDepth(root.right)+1
        if not root.right:
            return self.minDepth(root.left)+1
        return min(self.minDepth(root.right),self.minDepth(root.left))+1

        '''
    

root=TreeNode(3)
root.insertLeft(9)
root.insertRight(20)
root.right.insertLeft(15)
root.right.insertRight(7)
root.printTree()

result=Solution()
ans=result.minDepth(root)
print(ans)

## C++

#include<iostream>
#include<vector>
#include<queue>
using namespace std;

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

void InsertLeft(TreeNode* root, int data){
    TreeNode *tmp=root;
    if (tmp->left != nullptr)
        InsertLeft(root->left, data);
    else{
        TreeNode *new_left= new TreeNode(data);
        tmp->left=new_left;
    }
}

void InsertRight(TreeNode*root, int data){
    TreeNode *tmp=root;
    if (tmp->right != nullptr)
        InsertRight(root->right, data);
    else{
        TreeNode *new_right= new TreeNode(data);
        tmp->right=new_right;
    }
}

void PrintTree(TreeNode* root){
    TreeNode *tmp=root;
    vector<int> res;
    queue<TreeNode*> que;
    que.push(root);
    while (!que.empty()){
        TreeNode *curRoot=que.front(); que.pop();
        res.push_back(curRoot->val);
        if (curRoot->left)
            que.push(curRoot->left);
        if (curRoot->right)
            que.push(curRoot->right);
    }
    for (int i=0; i<res.size(); i++){
        cout<<res[i]<<" ";
    }
    cout<<endl;
}

class Solution{
public:
    bool isBalanced(TreeNode* root){
        if(root==nullptr)
            return true;
        bool balanced=true;
        height(root, &balanced);
        return balanced;
    }
    bool height(TreeNode* root, bool* balanced){
        if (!root)
            return 0;
        int hL=height(root->left, balanced);
        int hR=height(root->right,balanced);
        if (abs(hL-hR)>1){
            //call by reference get real value
            *balanced=false;
            return -1;
        }
        return max(hL,hR)+1;
    }
};

int main(){
    TreeNode *root= new TreeNode(3);
    InsertLeft(root,9);
    InsertRight(root,20);
    InsertLeft(root->right,15);
    InsertRight(root->right,7);
    PrintTree(root);

    Solution res;
    bool ans=res.isBalanced(root);
    cout<<ans<<endl;
    return 0;
}