给定一个二叉树,找出其最大深度。
二叉树的深度为根节点到最远叶子节点的距离。
给出一棵如下的二叉树:
1
/ \
2 3
/ \
4 5
这个二叉树的最大深度为 3
.
用递归分别遍历每个节点 ,返回相对于当前节点的最大深度(记得加上根节点)。
非递归写法可以用一个队列来存储,先将根节点存入,并记录当前节点的兄弟节点个数(指来自同一个父节点),当兄弟节点都出队列完毕,就对子节点进行与根节点同样的操作。
/**
* Definition of TreeNode:
* public class TreeNode {
* public int val;
* public TreeNode left, right;
* public TreeNode(int val) {
* this.val = val;
* this.left = this.right = null;
* }
* }
*/
public class Solution {
/**
* @param root: The root of binary tree.
* @return: An integer.
*/
public int maxDepth(TreeNode root) {
if (root == null)
return 0;
int left = maxDepth(root.left);
int right = maxDepth(root.right);
return Math.max(left, right) + 1;
}
//简化写法的话,其实可以一行代码解决:
// return root == null ? 0 : Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
}
/**
* Definition of TreeNode:
* public class TreeNode {
* public int val;
* public TreeNode left, right;
* public TreeNode(int val) {
* this.val = val;
* this.left = this.right = null;
* }
* }
*/
public class Solution {
/**
* @param root: The root of binary tree.
* @return: An integer.
*/
public int maxDepth(TreeNode root) {
if (root == null)
return 0;
Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.add(root);
int depth = 0; //表示二叉树的深度
int count = 0; //表示已从队列中取出当前层的个数
int amount = 1; //表示当前节点的兄弟节点个数
while (queue.size() != 0) {
TreeNode top = queue.poll();
count++;
if (top.left != null) {
queue.add(top.left);
}
if (top.right != null) {
queue.add(top.right);
}
if (count == amount) {
amount = queue.size();
count = 0;
depth++;
}
}
return depth;
}
}