题目
题目来源leetcode
leetcode地址：104. 二叉树的最大深度，难度：简单。
题目描述(摘自leetcode)：
给定一个二叉树，找出其最大深度。 二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。 说明: 叶子节点是指没有子节点的节点。 示例： 给定二叉树 [3,9,20,null,null,15,7]， 3 / \ 9 20 / \ 15 7 返回它的最大深度 3 。
题解
NO1：迭代遍历(递归)取深度
思路：使用迭代遍历递归方式来取得深度。
代码：
private int maxDepth = 0; //迭代遍历 public int maxDepth(TreeNode root) { recursionTreeDepth(root,0); return maxDepth; } public void recursionTreeDepth(TreeNode root,int depth){ if(root == null){ return; } //节点不为null，深度+1 depth++; if(depth>maxDepth){ maxDepth = depth; } //递归来遍历左、右节点 recursionTreeDepth(root.left,depth); recursionTreeDepth(root.right,depth); }
上面的递归处理不太精简，下面是重新进行编写的：
//递归遍历 public int maxDepth(TreeNode root) { //最底层 if(root == null){ return 0; } return Math.max(maxDepth(root.left),maxDepth(root.right))+1; }
NO2：迭代遍历(队列)
思路：本质就是迭代遍历一遍，中间过程统计一下栈的深度。
代码：
//迭代遍历 public int maxDepth(TreeNode root) { if(root == null){ return 0; } Deque<TreeNode> queue = new LinkedList<>(); queue.offer(root); int depth = 0; while(!queue.isEmpty()){ depth++;//深度统计 //当前层的节点数量 int size = queue.size(); //当前层的每个节点出队并且将其左右节点入队(不为null) while(size>0){ TreeNode node = queue.poll(); if(node.left != null){ queue.offer(node.left); } if(node.right != null){ queue.offer(node.right); } size--; } } return depth; }
