leetcode--104--二叉树的最大深度

题目：
给定一个二叉树，找出其最大深度。

二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

说明: 叶子节点是指没有子节点的节点。

示例：
给定二叉树 [3,9,20,null,null,15,7]，

    3
   / \
  9  20
    /  \
   15   7
返回它的最大深度 3 。

链接：https://leetcode-cn.com/problems/maximum-depth-of-binary-tree

思路：
1、模板题。按照广度优先算法进行遍历即可

Python代码：

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):

    def __init__(self):
        self.ret = []

    def maxDepth(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        if not root:
            return 0
        
        deque = [root]

        while deque:

            tmp = []
            nex = []
            for item in deque:
                tmp.append(item.val)
                if (item.left):
                    nex.append(item.left)
                if (item.right):
                    nex.append(item.right)
            deque = nex
            self.ret.append(tmp)
        return len(self.ret)

C++代码：

/**
 * 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:

    vector<vector<int> > ret;

    int maxDepth(TreeNode* root) {
        if (root==nullptr){
            return 0;
        }

        vector<TreeNode*> deque;
        deque.push_back(root);

        while(deque.size()>0){
            vector<int> tmp;
            vector<TreeNode*> nex;

            for (auto item:deque){
                tmp.push_back(item->val);
                if(item->left){
                    nex.push_back(item->left);
                }
                if(item->right){
                    nex.push_back(item->right);
                }
            }
            ret.push_back(tmp);
            deque.swap(nex);
        }
        return ret.size();
    }
};