LeetCode 104 Maximum Depth of Binary Tree

思路

分治算法。与求树的高度的写法基本一样。

代码

/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode(int x) { val = x; }* }*/
class Solution {
    // divide-and-conquerpublic 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;}
}

复杂度

时间复杂度O(n)
空间复杂度O(logn)