Catalog
  1. 1. 104. Maximum Depth of Binary Tree
LeetCode Solution: 104. Maximum Depth of Binary Tree

104. Maximum Depth of Binary Tree

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.

Note: A leaf is a node with no children.

Example:

Given binary tree [3,9,20,null,null,15,7],

1
2
3
4
5
  3
/ \
9 20
/ \
15 7

return its depth = 3.

解析

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
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
int maxDepth(TreeNode* root)
{
if (!root)
return 0;
int ldepth = 0;
int rdepth = 0;
ldepth = 1 + maxDepth(root->left);
rdepth = 1 + maxDepth(root->right);

return max(ldepth, rdepth);
}
};

利用了深搜的思想

  1. 如果当前为空指针就返回0
  2. 定义一个左树深度 一个右树深度
  3. 如果存在左树或者右树 就继续遍历 (加1表示当前所处为上一层的子树 当前层存在所以加1
  4. 因为不知道左树深还是右树深 返回左右树的最大值

只有遍历到最底层才会返回结果

算法只对树进行一次遍历 时间复杂度O(n)

Author: Jsthcit
Link: http://jsthcitpizifly.com/2020/06/15/LeetCode-Solution-104/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.
Donate
  • 微信
  • 支付寶