543. 二叉樹的直徑
給定一棵二叉樹郑什，你需要計(jì)算它的直徑長(zhǎng)度绕德。一棵二叉樹的直徑長(zhǎng)度是任意兩個(gè)結(jié)點(diǎn)路徑長(zhǎng)度中的最大值晃洒。這條路徑可能穿過(guò)也可能不穿過(guò)根結(jié)點(diǎn)。
示例 :
給定二叉樹
1
/ \
2 3
/ \
4 5
返回 3, 它的長(zhǎng)度是路徑 [4,2,1,3] 或者 [5,2,1,3]。
注意：兩結(jié)點(diǎn)之間的路徑長(zhǎng)度是以它們之間邊的數(shù)目表示。
/**
* 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 diameterOfBinaryTree(TreeNode* root) {
int ans = 0,depth = 0;
dfs(root, ans, depth);
return ans - 1;
}
int dfs(TreeNode* node, int& ans, int depth) {
if (node == nullptr) return 0;
int leftV = dfs(node->left, ans, depth);
int rightV = dfs(node->right, ans, depth);
ans = max(ans, leftV + rightV + 1);
return max(leftV , rightV) + 1; //此節(jié)點(diǎn)作為子樹的深度
}
};
