LeetCode Algorithm 543. 二叉树的直径

543. 二叉树的直径

Ideas

这题貌似也在左神算法里见过。

基本思想就是递归，根节点从左子树获得一个想要的信息，从右子树获得一个想要的信息，然后对两个信息进行处理。

其实可以把直径分成两半看：从根节点到左子树的叶子结点的最长路径+根节点到右子树的叶子结点的最长路径-1。

然后就简单了，问题就转变成了求二叉树的深度。

Code C++

class Solution { int ans = 1; int depth(TreeNode* rt) { if (rt == NULL) { return 0; } int l_depth = depth(rt->left); int r_depth = depth(rt->right); ans = max(ans, l_depth + r_depth + 1); return max(l_depth, r_depth) + 1; } public: int diameterOfBinaryTree(TreeNode* root) { depth(root); return ans - 1; } };