040二叉树的直径

二叉树的直径题目链接https://leetcode.cn/problems/diameter-of-binary-tree/description/?envTypestudy-plan-v2envIdtop-100-liked我的解答无分析自己没有什么思路。看了官方题解后的解答int ans; public int diameterOfBinaryTree(TreeNode root) { ans0; depth(root); return ans;//二叉树的最长路径节点数减一就是二叉树的直径 } public int depth(TreeNode node){ if(node null){ return 0; } int L depth(node.left);//当前节点的左子树的最大深度 int R depth(node.right);//当前节点的右子树的最大深度 ans Math.max(ans, LR);//一定经过当前节点的最长路径经过的节点数 return Math.max(L,R)1;//返回以当前节点为根节点的子树的最大深度 }分析​ 1、代码的时间复杂度为O(n)空间复杂度为O(Height)其中 Height 为二叉树的高度。​ 2、首先明确求二叉树的直径就是找出二叉树中的最长路径长度最长路径经过的节点数减一最长路径不一定会经过二叉树的根节点。但是当我们固定路径中包含某个节点时经过这个节点的最长路径长度假设为maxDepth只与左子树的最大深度假设为L和右子树的最大深度假设为R有关即maxDepthLR。所以我们只需要维护每个节点左右子树的最大深度每次取最大最终得到的结果就是答案。总结本题解题的本质思路就是根据每个节点左边的最长路径拼接上右边的最长路径组成经过该节点的最长路径将每个节点的最长路径作比较取最大值就是二叉树的最长路径即二叉树的直径。