LeetCode 543 Diameter of Binary Tree
概述
https://leetcode.com/problems/diameter-of-binary-tree/
后续遍历
借求最大深度时计算通过该节点的最大路径长度。
要注意的是,路径长度为路径上节点个数减一,即 d = leftMaxDepth + rightMaxDepth + 1 - 1
。
class Solution {
public:
int maxD = 0;
int diameterOfBinaryTree(TreeNode* root) {
maxDepth(root);
return maxD;
}
int maxDepth(TreeNode* root) {
if (!root) return 0;
int ld = maxDepth(root->left);
int rd = maxDepth(root->right);
int d = ld + rd;
maxD = max(maxD, d);
return max(ld, rd) + 1;
}
};