给定一个二叉树的根节点,返回其最大深度。 二叉树的最大深度是从根节点到最远叶子节点沿着最长路径的节点数。
时间: 2023-08-26 13:07:09 浏览: 47
好的,您可以调用以下代码实现:
```python
class Solution:
def maxDepth(self, root: TreeNode) -> int:
if not root:
return 0
left_depth = self.maxDepth(root.left)
right_depth = self.maxDepth(root.right)
return max(left_depth, right_depth) + 1
```
其中,`root` 为二叉树的根节点,`TreeNode` 为二叉树节点的定义结构体。首先判断根节点是否为空,如果为空,返回深度为0;如果不为空,则递归求左子树和右子树的深度,再取其中的较大值,最后再加上1,就可以求得整个二叉树的最大深度了。
相关问题
给定一个二叉树,求二叉树从根节点到叶节点路径和最大值
思路:遍历二叉树,每到一个节点就更新当前路径的和,如果当前节点是叶节点,则将当前路径的和与最大值比较并更新最大值。最终返回最大值即可。
代码如下:
```python
class Solution:
def maxPathSum(self, root: TreeNode) -> int:
self.max_sum = float('-inf') # 记录最大值
self.dfs(root, 0)
return self.max_sum
def dfs(self, root, curr_sum):
if not root:
return
curr_sum += root.val
if not root.left and not root.right: # 叶节点
self.max_sum = max(self.max_sum, curr_sum)
self.dfs(root.left, curr_sum)
self.dfs(root.right, curr_sum)
```
时间复杂度:$O(n)$,遍历了整个二叉树。空间复杂度:$O(h)$,递归深度最大为树的高度。
用c语言,给定一个二叉树,求二叉树从根节点到叶节点路径和最大值
#include <stdio.h>
#include <stdlib.h>
struct TreeNode {
int val;
struct TreeNode* left;
struct TreeNode* right;
};
int maxPathSum(struct TreeNode* root) {
if (root == NULL) return 0;
int leftMax = maxPathSum(root->left); // 左子树的最大路径和
int rightMax = maxPathSum(root->right); // 右子树的最大路径和
int maxSum = root->val; // 当前节点的最大路径和
if (leftMax > 0) maxSum += leftMax;
if (rightMax > 0) maxSum += rightMax;
return maxSum;
}
int main() {
// 创建二叉树
struct TreeNode* root = (struct TreeNode*)malloc(sizeof(struct TreeNode));
root->val = 1;
root->left = (struct TreeNode*)malloc(sizeof(struct TreeNode));
root->left->val = 2;
root->left->left = NULL;
root->left->right = NULL;
root->right = (struct TreeNode*)malloc(sizeof(struct TreeNode));
root->right->val = 3;
root->right->left = (struct TreeNode*)malloc(sizeof(struct TreeNode));
root->right->left->val = 4;
root->right->left->left = NULL;
root->right->left->right = NULL;
root->right->right = (struct TreeNode*)malloc(sizeof(struct TreeNode));
root->right->right->val = 5;
root->right->right->left = NULL;
root->right->right->right = NULL;
int maxSum = maxPathSum(root);
printf("The maximum path sum is %d\n", maxSum);
return 0;
}