剑指 Offer.55-二叉树的深度
剑指 Offer.55-二叉树的深度
题目链接
<剑指 Offer 55 - I. 二叉树的深度>
问题描述
输入一棵二叉树的根节点,求该树的深度。从根节点到叶节点依次经过的节点(含根、叶节点)形成树的一条路径,最长路径的长度为树的深度。
个人解法(BFS + 计数)
使用层序遍历
,每次遍历一层将depth
加1,在遍历完整棵二叉树的时候返回当前二叉树的深度
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
| class Solution { public int maxDepth(TreeNode root) { if(root == null) return 0; int depth = 0; Queue<TreeNode> queue = new LinkedList<TreeNode>(); queue.offer(root); while(!queue.isEmpty()){ int queueSize = queue.size(); depth++; for(int i=0;i<queueSize;i++){ TreeNode element = queue.poll(); if(element.left!=null){ queue.offer(element.left); }
if(element.right!=null){ queue.offer(element.right); } } }
return depth; } }
|
另一种解法(DFS)
二叉树的深度 = 左右子树的最大深度,通过后序遍历
,持续左右节点的最大深度即可
代码
1 2 3 4 5 6
| class Solution { public int maxDepth(TreeNode root) { if(root == null) return 0; return Math.max(maxDepth(root.left),maxDepth(root.right))+1; } }
|