给定一个二叉树,找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。
示例:
给定二叉树 [3,9,20,null,null,15,7]
,
3
/ \
9 20
/ \
15 7
返回它的最大深度 3 。
题解1
遍历法,隐式回溯
/**
* 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 res = 0;
int maxDepth(TreeNode* root) {
if (root == nullptr) {
return 0;
}
helper(root, 0);
return res;
}
void helper(TreeNode* root, int depth) {
if (root == nullptr) {
res = max(res, depth);
return;
}
helper(root->left, depth + 1);
helper(root->right, depth + 1);
}
};
每次左、右走的时候,都把depth
加1,因为是在参数里面加的,所以递归会为我们自动的完成回溯,不需要显示回溯了。
题解2
遍历法,显式回溯
/**
* 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 res = 0;
int maxDepth(TreeNode* root) {
if (root == nullptr) {
return 0;
}
helper(root, 0);
return res;
}
void helper(TreeNode* root, int depth) {
if (root == nullptr) {
res = max(res, depth);
return;
}
++depth;
helper(root->left, depth);
--depth;
++depth;
helper(root->right, depth);
--depth;
}
};
depth
每次都在传参之前改变,所以说每次从左、右递归回来,都需要手动显式回溯,否则就会出现重复计算的问题。也可以把遍历左、右之间depth
的操作省去,因为减和加正好抵消了,但是就隐藏了具体细节。本着清楚透彻的原则,多写点没关系。
当然上面是针对空节点作为base case,也可以再加上叶子节点作为base case,这都无伤大雅,思路是一样的,换汤不换药而已。
/**
* 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 res = 0;
int maxDepth(TreeNode* root) {
if (root == nullptr) {
return 0;
}
helper(root, 0);
return res;
}
void helper(TreeNode* root, int depth) {
if (root == nullptr) {
return;
}
if (root->left == nullptr && root->right == nullptr) {
res = max(res, depth + 1);
return;
}
++depth;
helper(root->left, depth);
--depth;
++depth;
helper(root->right, depth);
--depth;
}
};
题解3
分治法
/**
* 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 == nullptr) {
return 0;
}
auto left = maxDepth(root->left);
auto right = maxDepth(root->right);
return 1 + max(left, right);
}
};
- leetcode Maximum Binary Depth Treemaximum binary depth tree leetcode maximum binary depth maximum-width-of-binary-tree leetcode problems binary-tree-maximum-path-sum leetcode maximum maximum-width-of-binary-tree binary-tree-maximum-path-sum binary tree complete binary 321e tree traversal preorder binary tree postorder traversal binary tree