###### tags: `Leetcode` `easy` `tree` `python` `c++` `Top 100 Liked Questions`

# 104. Maximum Depth of Binary Tree

## [題目出處:] https://leetcode.com/problems/maximum-depth-of-binary-tree/

## 題目:
Given the root of a binary tree, return its maximum depth.

A binary tree's maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

## 解題思路:
遞迴即可~

## 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 maxDepth(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        if not root:
            return 0
        else:
            return max(self.maxDepth(root.left),self.maxDepth(root.right))+1
        
if __name__ == '__main__':
    root=TreeNode(3)
    root.insertLeft(9)
    root.insertRight(20)
    root.right.insertLeft(15)
    root.right.insertRight(7)
    root.printTree()
    

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

## C++:

#include<iostream>
#include<queue>
#include<vector>
#include<stack>
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;
    while( tmp->left != nullptr){
        tmp=tmp->left;
    }
    TreeNode *new_Left = new TreeNode(data);
    tmp->left=new_Left;
}

void insertRight(TreeNode *root, int data){
    TreeNode *tmp=root;
    while (tmp->right != nullptr){
        tmp=tmp->right;
    }
    TreeNode *new_Right= new TreeNode(data);
    tmp->right=new_Right;
}

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

class Solution {
public:
    int maxDepth(TreeNode* root) {
        if (root==nullptr)
            return 0;
        return max(maxDepth(root->left),maxDepth(root->right))+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;
    int ans=res.maxDepth(root);
    cout<<ans<<endl;
    return 0;
}