在用递归求左右子树的高度的同时,就将左右子树的高度之和与max比较,并持续更新max,最后的max即为两个结点之间的最大距离。
int max = 0; //max作为全局变量,不断在更新
int depth(struct TreeNode* node){
if(node == NULL)
return 0;
int left_depth = depth(node->left);
int right_depth = depth(node->right);
if(max < left_depth + right_depth)
max = left_depth + right_depth;
return left_depth > right_depth ? left_depth+1 : right_depth+1;
}
int diameterOfBinaryTree(struct TreeNode* root ) {
max = 0;
depth(root);
return max;
}

京公网安备 11010502036488号