题目描述
- 输入一颗二叉树的根节点，求该树的深度。从根节点到叶节点依次经过的节点形成的一条路径，最长路径的长度为该二叉树的深度。
解题思路一：
- 递归：通过递归分别求得左子树和右子树的深度，取其最大值即为该树的深度。
解题思路二：
- 非递归：可通过二叉树的层序遍历来实现，遍历的层数，即为二叉树的深度。
代码
class TreeNode{
int value;
TreeNode left;
TreeNode right;
TreeNode(int val){
this.value = val;
}
}
/**
* 递归解法
*/
int treeDepth(TreeNode root) {
if (root == null) {
return 0;
}
int leftDepth = treeDepth(root.left);
int rightDepth = treeDepth(root.right);
return leftDepth > rightDepth ? leftDepth + 1: rightDepth + 1;
}
/**
* 非递归解法
*/
int treeDepthV2(TreeNode root) {
if (root == null) {
return 0;
}
//非递归需要借助队列来实现
LinkedList<TreeNode> queue = new LinkedList<>();
queue.offer(root);
int depth = 0;
while (!queue.isEmpty()) {
int size = queue.size();//size即该层节点的数量
depth ++ ;
System.out.println();
for (int i = 0; i < size; i++) {
TreeNode cur = queue.poll();
System.out.print(cur.value + " ");
if (cur.left != null) {
queue.offer(cur.left);
}
if (cur.right != null) {
queue.offer(cur.right);
}
}
}
System.out.println();
return depth;
}
