大气网站模板下载,动画设计毕业作品搞笑,网站建设需要什么人才,二级建造师考试class Solution {
public:// 定义一个变量 maxd#xff0c;用于存储当前二叉树的最大直径。int maxd 0; // 主函数#xff0c;计算二叉树的直径。int diameterOfBinaryTree(TreeNode* root) {// 调用 maxDepth 函数进行递归计算#xff0c;并更新 maxd。maxDepth(root);// …class Solution {
public:// 定义一个变量 maxd用于存储当前二叉树的最大直径。int maxd 0; // 主函数计算二叉树的直径。int diameterOfBinaryTree(TreeNode* root) {// 调用 maxDepth 函数进行递归计算并更新 maxd。maxDepth(root);// 返回计算得到的最大直径。return maxd;}// 定义 maxDepth 函数计算二叉树的深度同时更新直径。public:int maxDepth(TreeNode* root) {// 如果当前节点为空则返回深度为 0。if (root nullptr) {return 0;}// 递归计算左子树的深度。int l_depth maxDepth(root-left);// 递归计算右子树的深度。int r_depth maxDepth(root-right);// 更新最大直径通过当前节点的左右子树深度之和来计算路径长度。maxd max(l_depth r_depth, maxd);// 返回当前节点的最大深度左右子树深度的最大值 当前节点。return max(l_depth, r_depth) 1;}
}; 假设我们有一个二叉树如下 1 / \ 2 3 / \ 4 5 运行过程
1. 初始化阶段
• maxd 0
• 调用 diameterOfBinaryTree(root)其中 root 指向节点 1。
2. 递归展开 maxDepth(root)
• 以节点 1 为根计算左子树和右子树的深度。 左子树递归以 2 为根
• 调用 maxDepth(root-left)进入节点 2。 左子树的左子树递归以 4 为根
• 调用 maxDepth(root-left-left)进入节点 4。
• 节点 4 的左右子树为空
• 调用 maxDepth(root-left-left-left) 返回 0。
• 调用 maxDepth(root-left-left-right) 返回 0。
• 通过节点 4 的路径长度为 0 0 0。
• maxd max(0, maxd) 0。
• 返回节点 4 的深度max(0, 0) 1 1。 左子树的右子树递归以 5 为根
• 调用 maxDepth(root-left-right)进入节点 5。
• 节点 5 的左右子树为空
• 调用 maxDepth(root-left-right-left) 返回 0。
• 调用 maxDepth(root-left-right-right) 返回 0。
• 通过节点 5 的路径长度为 0 0 0。
• maxd max(0, maxd) 0。
• 返回节点 5 的深度max(0, 0) 1 1。 回到节点 2
• 左子树深度为 1节点 4。
• 右子树深度为 1节点 5。
• 通过节点 2 的路径长度为 1 1 2。
• maxd max(2, maxd) 2。
• 返回节点 2 的深度max(1, 1) 1 2。 右子树递归以 3 为根
• 调用 maxDepth(root-right)进入节点 3。
• 节点 3 的左右子树为空
• 调用 maxDepth(root-right-left) 返回 0。
• 调用 maxDepth(root-right-right) 返回 0。
• 通过节点 3 的路径长度为 0 0 0。
• maxd max(0, maxd) 2。
• 返回节点 3 的深度max(0, 0) 1 1。 回到节点 1
• 左子树深度为 2节点 2。
• 右子树深度为 1节点 3。
• 通过节点 1 的路径长度为 2 1 3。
• maxd max(3, maxd) 3。
• 返回节点 1 的深度max(2, 1) 1 3。 结果
• 最终maxd 3表示二叉树的最大直径为 3。
• 返回值为 3。 递归总结
• 每次递归调用时我们计算左右子树的深度并利用它们更新全局变量 maxd。
• maxDepth 返回的是当前节点的深度而 maxd 更新的是路径长度左深度 右深度。
