leetcode解题: Maximum Depth of Binary Tree (104)

发表于 | 分类于

Given a binary tree, find its maximum depth.

The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

解法1：Recursion with O(N) time

Divide and Conquer, 递归的思路，空Node的depth为0，任意一个Node的depth为左面和右面的最大的depth+1, i.e. maxDepth(i) = Max(maxDepth(left), maxDepth(right)) + 1
注意C++中空值是NULL, java是null
C++

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    int maxDepth(TreeNode* root) {
        if (root == NULL) {
            return 0;
        }
        return max(maxDepth(root->left), maxDepth(root->right)) + 1;
    }
};

Java

1
2
3
4
5
6
7
8
9
public class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
    }
}

解法2: Non-recursion

我们只需要修改一个非递归的树的遍历算法就可以了，这篇文章详细讲了思路