NC13 二叉树的最大深度（迭代）

- 题目描述：

- 题目链接：
https://www.nowcoder.com/practice/8a2b2bf6c19b4f23a9bdb9b233eefa73?tpId=188&&tqId=36522&rp=1&ru=/ta/job-code-high-week&qru=/ta/job-code-high-week/question-ranking

- 设计思想：

详细操作流程看下图

-视频讲解链接B站视频讲解

- 代码：
c++版本:

 /**
 * struct TreeNode {
 *    int val;
 *    struct TreeNode *left;
 *    struct TreeNode *right;
 * };
 */

class Solution {
public:
    /**
     * 
     * @param root TreeNode类 
     * @return int整型
     */
    int maxDepth(TreeNode* root) {
        if(root == NULL) return 0; //根点为空返回0
        queue<TreeNode*>q; //开一个队列用于存储遍历树的节点
        int res = 0; //用来存最大高度
        q.push(root);
        int n = 0; //用来存储队列的大小
        while(!q.empty()){ //队列不为空就进行如下操作
            n = q.size();
            for(int i = 0;i < n;i ++){ //将这一层节点的左右孩子全部入队列
                TreeNode* node = q.front(); //取出队列的第一个元素
                q.pop();
                if(node->left) q.push(node->left); //左孩子如果不为空就进队列
                if(node->right) q.push(node->right); //右孩子如果不为空就进队列
            }
            res ++; //每遍历一层res就++
        }
        return res;

    }
};

Java版本：

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 * }
 */

public class Solution {
    /**
     * 
     * @param root TreeNode类 
     * @return int整型
     */
    public int maxDepth (TreeNode root) {
        if(root == null) return 0; //节点为空返回0
        Queue<TreeNode> q = new LinkedList<TreeNode>(); //开一个队列用于存储遍历树的节点
        q.add(root);
        int n = 0; //用来存储队列的大小
        int res = 0; //用来存最大高度
        while(!q.isEmpty()){ //队列不为空就进行如下操作
            n = q.size();
            for(int i = 0;i < n;i ++){
                TreeNode node = q.poll();//取出队列的第一个元素
                if(node.left != null) q.add(node.left); //左孩子如果不为空就进队列
                if(node.right != null) q.add(node.right); //右孩子如果不为空就进队列
            }
            res ++; //每遍历一层res就++
        }
        return res;

    }
}

Python版本:

# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

#
# 
# @param root TreeNode类 
# @return int整型
#
import queue
class Solution:
    def maxDepth(self , root ):
        # write code here
        if not root : return 0 #节点为空返回0
        q = queue.Queue(); #开一个队列用于存储遍历树的节点
        q.put(root)
        n,res =0,0
        while q.qsize() > 0: #队列不为空就进行如下操作
            n = q.qsize()
            for i in range(n): #将这一层节点的左右孩子全部入队列
                node = q.get() #取出队列的第一个元素
                if node.left:
                    q.put(node.left)#左孩子如果不为空就进队列
                if node.right:
                    q.put(node.right)#右孩子如果不为空就进队列
            res += 1 #每遍历一层res就++

        return res