已知平衡二叉树（AVL 树）的定义为：树中任意一个节点的左右子树的高度差的绝对值不超过 1，且左右子树均为平衡二叉树。若某平衡二叉树的高度为 4（根节点的高度记为 1），则其根节点的左右子树的节点数之差最多为（ ）

A. 1 B. 2 C. 3 D. 5

[tag_link]

正确答案：D

**【解析】**平衡二叉树高度为 4（根节点高度为 1），因此左右子树的高度组合为：

• 两者均为 3，或
• 一个为 3、另一个为 2。为最大化节点数之差，应使较高子树取最大节点数，较低子树取最小节点数。
• 高度 3 的平衡二叉树最大节点数为 7（满二叉树），
• 高度 2 的最小节点数为 2（根节点加一个子节点），此时节点数之差为7−2=5。若左右子树高度均为 3，节点数之差最大为7−4=3。因此，根节点的左右子树节点数之差最多为 5。