有 1000 个酒瓶，其中一个瓶子里装着有毒的酒，如果老鼠喝了有毒的酒一小时就会死掉。给你一小时至少需要多少只老鼠才能找出哪个瓶子里有毒？
思考半分钟再来看答案：
其实这题很简单，我们只需要把所有的酒瓶编上号，用二进制表示， 1000 个酒瓶只需要 10 个二进制位就够了，因为 2^10=1024，大于 1000 了，所以至少需要 10 只老鼠。
任何一个酒瓶的二进制位中如果右边第 1 位是 1 ，就让第 1 只老鼠尝，如果右边第 2 位是 1 ，就让第 2 只老鼠尝，如果右边第 n 位是 1 ，就让第 n 只老鼠尝。。。
假如一个小时之后第 1 ，3，5 这三只老鼠死了，说明二进制位中右边第 1 ，3，5 位肯定是 1 ，也就是 0000010101(总共 10 位)，转化为二进制就是 21 ，也就是第 21 个酒瓶肯定是有毒的。
--------------下面是今天的算法题--------------
来看下今天的算法题，这题是LeetCode的第543题：二叉树的直径。
问题描述
来源：LeetCode第543题
难度：简单
给你一棵二叉树的根节点，返回该树的直径。二叉树的直径是指树中任意两个节点之间最长路径的长度。这条路径可能经过也可能不经过根节点 root 。两节点之间路径的长度由它们之间边数表示。
示例1：
输入：root = [1,2,3,4,5] 输出：3 解释：3 ，取路径 [4,2,1,3] 或 [5,2,1,3] 的长度。
树中节点数目在范围 [1, 10^4] 内
-100 <= Node.val <= 100
问题分析
这题让计算二叉树的直径，实际上就是让计算 二叉树中任意节点两个子树的高度和，保存最大值即可 。
比如示例 1 中，根节点左子树的高度是 2 ，根节点右子树的高度是 1 ，它们的和是 3 ，这个就是该二叉树的最大直径。
二叉树的最大直径不一定会经过根节点，我们需要计算每一个节点左右子树的高度和，可以参考二叉树的后续遍历，从下往上的方式计算。
JAVA：
int ans = 0;
public int diameterOfBinaryTree(TreeNode root) {
maxDepth(root);
return ans;
}
// 计算当前节点的高度
private int maxDepth(TreeNode root) {
if (root == null)
return 0;
int left = maxDepth(root.left);// 左子树高度
int right = maxDepth(root.right);// 右子树高度
ans = Math.max(ans, left + right);// 保存最大值
return Math.max(left, right) + 1;// 返回子树的高度
}C++：
public:
int ans = 0;
int diameterOfBinaryTree(TreeNode *root) {
maxDepth(root);
return ans;
}
// 计算当前节点的高度
int maxDepth(TreeNode *root) {
if (root == nullptr)
return 0;
int left = maxDepth(root->left);// 左子树高度
int right = maxDepth(root->right);// 右子树高度
ans = max(ans, left + right);// 保存最大值
return max(left, right) + 1;// 返回子树的高度
}Python：
def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
ans = 0
# 计算当前节点的高度
def maxDepth(node):
if node is None:
return 0
left = maxDepth(node.left) # 左子树高度
right = maxDepth(node.right) # 右子树高度
nonlocal ans
ans = max(ans, left + right) # 保存最大值
return max(left, right) + 1 # 返回子树的高度
maxDepth(root)
return ans笔者简介
博哥，真名：王一博，毕业十多年， 作者，专注于 数据结构和算法 的讲解，在全球30多个算法网站中累计做题2000多道，在公众号中写算法题解800多题，对算法题有自己独特的解题思路和解题技巧，喜欢的可以给个关注，也可以 下载我整理的1000多页的PDF算法文档 。
热门跟贴