【算法14】-【二叉树的最大深度】
总结
了解递归并利用递归解决问题并不容易。1、当遇到树问题时,请先思考一下两个问题:
1)你能确定一些参数,从该节点自身解决出发寻找答案吗?
2)你可以使用这些参数和节点本身的值来决定什么应该是传递给它子节点的参数吗?
如果答案都是肯定的,那么请尝试使用 “自顶向下” 的递归来解决此问题。
2、或者你可以这样思考:对于树中的任意一个节点,如果你知道它子节点的答案,你能计算出该节点的答案吗? 如果答案是肯定的,那么 “自底向上” 的递归可能是一个不错的解决方法。
方法一:递归
public int maxDepth(TreeNode root) { if (root == null) { return 0; } else { int leftHeight = maxDepth(root.left); int rightHeight = maxDepth(root.right); return Math.max(leftHeight, rightHeight) + 1; } }
方法二:广度优先搜索
class Solution { public int maxDepth(TreeNode root) { if (root == null) { return 0; } Queue<TreeNode> queue = new LinkedList<TreeNode>(); queue.offer(root); int ans = 0; while (!queue.isEmpty()) { int size = queue.size(); while (size > 0) { TreeNode node = queue.poll(); if (node.left != null) { queue.offer(node.left); } if (node.right != null) { queue.offer(node.right); } size--; } ans++; } return ans; } }