vlambda博客
学习文章列表

给定一个二叉树，找出其最大深度。

二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

说明: 叶子节点是指没有子节点的节点。

示例：

给定二叉树 [3,9,20,null,null,15,7]

1public class TreeNode {
2    int val;
3    TreeNode left;
4    TreeNode right;
5
6    TreeNode(int x) {
7        val = x;
8    }
9}

1struct TreeNode {
2    int val;
3    struct TreeNode *left;
4    struct TreeNode *right;
5};

1struct TreeNode {
2    int val;
3    TreeNode *left;
4    TreeNode *right;
5    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
6};

我们能想到的最简单的方式估计就是递归了，也就是下面这个图

如果对递归不熟悉的话可以看下我前面讲的关于复仇一个故事。下面我们来画个图来分析下

看明白了上面的过程，代码就容易多了，我们看下

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

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

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

除了递归，我们还可能想到的就是BFS（宽度优先搜索算法（又称广度优先搜索）），他的实现原理就是一层层遍历，统计一下总共有多少层，我们来画个图分析一下。

一层一层往下走，统计总共有多少层，我们来看下代码

 1public int maxDepth(TreeNode root) {
 2    if (root == null)
 3        return 0;
 4    Deque<TreeNode> stack = new LinkedList<>();
 5    stack.push(root);
 6    int count = 0;
 7    while (!stack.isEmpty()) {
 8        int size = stack.size();
 9        while (size-- > 0) {
10            TreeNode cur = stack.pop();
11            if (cur.left != null)
12                stack.addLast(cur.left);
13            if (cur.right != null)
14                stack.addLast(cur.right);
15        }
16        count++;
17    }
18    return count;
19}

 1public:
 2int maxDepth(TreeNode* root) {
 3    if (root == NULL)
 4        return 0;
 5    int res = 0;
 6    queue<TreeNode *>q;
 7    q.push(root);
 8    while (!q.empty()) {
 9        ++res;
10        for (int i = 0, n = q.size(); i < n; ++i) {
11            TreeNode * p = q.front();
12            q.pop();
13            if (p -> left != NULL)
14                q.push(p -> left);
15            if (p -> right != NULL)
16                q.push(p -> right);
17        }
18    }
19    return res;
20}

想到BFS我们一般会和DFS联想到一起，DFS是深度优先搜索算法，我们先来看下代码

 1public int maxDepth(TreeNode root) {
 2    if (root == null)
 3        return 0;
 4    Stack<TreeNode> stack = new Stack<>();
 5    Stack<Integer> value = new Stack<>();
 6    stack.push(root);
 7    value.push(1);
 8    int max = 0;
 9    while (!stack.isEmpty()) {
10        TreeNode node = stack.pop();
11        int temp = value.pop();
12        max = Math.max(temp, max);
13        if (node.left != null) {
14            stack.push(node.left);
15            value.push(temp + 1);
16        }
17        if (node.right != null) {
18            stack.push(node.right);
19            value.push(temp + 1);
20        }
21    }
22    return max;
23}

 1public:
 2int maxDepth(TreeNode*root) {
 3    if (root == NULL)
 4        return 0;
 5    stack<TreeNode *>nodeStack;
 6    stack<int> value;
 7    nodeStack.push(root);
 8    value.push(1);
 9    int max = 0;
10    while (!nodeStack.empty()) {
11        TreeNode * node = nodeStack.top();
12        nodeStack.pop();
13        int temp = value.top();
14        value.pop();
15        max = temp > max ? temp : max;
16        if (node -> left != NULL) {
17            nodeStack.push(node -> left);
18            value.push(temp + 1);
19        }
20        if (node -> right != NULL) {
21            nodeStack.push(node -> right);
22            value.push(temp + 1);
23        }
24    }
25    return max;
26}

这里使用了两个栈，一个是存储节点的，一个是存储每个节点到根节点总共经过多少个节点（包含根节点和当前节点）。