Leetcode刷题100天—104. 二叉树的最大深度(二叉树)—day08

落日映苍穹つ 2022-09-09 14:54 135阅读 0赞

前言：

> 作者：神的孩子在歌唱
> 
> 大家好，我叫运智

![image-20210902104605750][]

#### [104. 二叉树的最大深度][104.] ####

难度简单956收藏分享切换为英文接收动态反馈

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

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

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

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

3
       / \
      9  20
        /  \
       15   7

返回它的最大深度 3 。

package 二叉树;
    
    import java.util.LinkedList;
    import java.util.Queue;
    
    /* * 6 * https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/ */
    public class _104_二叉树的最大深度 { 
    // 递归:使用深度优先遍历（从下到上）,先遍历左子树,在遍历右子树
    	public int maxDepth(TreeNode root) { 
    			if (root==null) { 
    				return 0;
    			}
    			int leftHeight=maxDepth(root.left);
    			int rightHeight=maxDepth(root.right);
    // 比较左右子树那个深度大,将那个大的子树加一,不断递归
    			return Math.max(leftHeight,rightHeight)+1;
        }
    // 迭代：广度优先遍历（从上到下），左右子树同时遍历，更层序遍历差不多
    	public int maxDepth2(TreeNode root) { 
    		if (root==null) { 
    			return 0;
    		}
    // 创建一个队列
    		Queue<TreeNode> queue=new LinkedList<TreeNode>();
    // 首先将根节点入队
    		queue.offer(root);
    // 设置深度
    		int ans=0;
    		while(!queue.isEmpty()) { 
    
    // 获取队列大小
    			int queue_size=queue.size();
    // 遍历之前队中的数据
    			for(int i=0;i<queue_size;i++) { 
    //出队
    				TreeNode node=queue.poll();
    // 获取左右子树
    				if (node.left!=null) { 
    					queue.offer(node.left);
    				}
    				if (node.right!=null) { 
    					queue.offer(node.right);
    				}
    			}
    			ans++;
    		}
    		return ans;
    	}
    }

> 本人csdn博客：https://blog.csdn.net/weixin\_46654114
> 
> 转载说明：跟我说明，务必注明来源，附带本人博客连接。

[image-20210902104605750]: /images/20220829/3b1cc16291be44bf8e89d9316d5afd49.png
[104.]: https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/