在用递归求左右子树的高度的同时,就将左右子树的高度之和与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; }