1. 题意

求二叉树上最远两个节点之间的距离。

2. 题解

2.1 暴力

最长路径的三种情况

• 通过根节点
• 在左子树
• 在右子树

            12    4     5  6  7   8   9 diameter =  5

通过根节点的最长路径长度一定是左右子树深度之和。

但是这样求左右子树的深度会不断重复，所以复杂度很高。

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:int getDepth(TreeNode *root) {return root == nullptr ? 0 : max(getDepth(root->left), getDepth(root->right)) + 1;}int diameterOfBinaryTree(TreeNode* root) {// 最长路径的三种情况
// * 通过根节点
// * 在左子树
// * 在右子树//          1
//       2    
//     4  5  
//  6 7  8 9
// diameter =  5if ( nullptr == root)return 0;int lmx = diameterOfBinaryTree(root->left);int rmx = diameterOfBinaryTree(root->right);int ans = max(lmx, rmx);int ldepth = getDepth(root->left);int rdepth = getDepth(root->right);return max(ans, ldepth + rdepth); }
};

2.2 动态规划

我们可以在求深度的时候，更新答案，返回经过根节点但不拐弯的链的最长长度。

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:// 自底向上求出，经过当前节点的最大深度// 并统计经过当前节点的路径长度// 返回经过子树的深度int getDepth(TreeNode *root, int &ans) {if ( nullptr == root)return 0;int ldepth = getDepth(root->left, ans);int rdepth = getDepth(root->right, ans);ans = max( ldepth + rdepth + 1, ans);return max(ldepth, rdepth) + 1;}int diameterOfBinaryTree(TreeNode* root) {int ans = 0;getDepth(root, ans);return ans - 1;}
};