力扣HOT100(45) 二叉树的直径

任意一条路径都可以看作是以某个节点为 “拐点”左边接左子树的最深路径右边接右子树的最深路径。比如路径4→2→1→3的拐点是节点 1左子树最深路径1→2→42 条边右子树最深路径1→31 条边总路径长度213边数所以我们的目标转化为遍历树中所有节点计算每个节点作为 “拐点” 时的路径长度取所有路径长度的最大值就是整棵树的直径完整解题步骤1. 定义两个核心变量depth(node)递归函数返回以node为根的子树的深度节点数ans全局变量记录所有节点作为拐点时路径经过的节点数最大值2. 递归函数depth(node)的逻辑终止条件如果node是空节点返回 0空树深度为 0递归左子树得到左子树深度L递归右子树得到右子树深度R更新最大值当前节点作为拐点的路径节点数 L R 11 是加上当前节点本身用这个值更新ans返回当前子树深度max(L, R) 1当前节点 左右子树中更深的那个3. 主函数逻辑初始化ans 1至少有一个节点路径节点数为 1调用depth(root)遍历整棵树最终直径 ans - 1因为边数 节点数 - 1class Solution { int ans; // 全局变量记录所有路径的节点数最大值 // 递归函数返回以rt为根的子树的深度节点数 int depth(TreeNode* rt){ // 1. 终止条件空节点深度为0 if (rt NULL) { return 0; } // 2. 先算左子树深度 int L depth(rt-left); // 3. 再算右子树深度 int R depth(rt-right); // 4. 关键计算当前节点作为拐点的路径节点数更新最大值 ans max(ans, L R 1); // 5. 返回当前子树的深度左右子树中更深的那个 当前节点 return max(L, R) 1; } public: int diameterOfBinaryTree(TreeNode* root) { ans 1; // 初始化为1对应只有一个节点的情况 depth(root); // 遍历整棵树 return ans - 1; // 节点数最大值减1得到边数直径 } };