卷別

資料結構與演算法

選擇

國立臺灣大學 2024 · 考試 · 第 9 題

(5 points) We have a binary tree $T$ and for every node $v \in T$ , we want to compute the new height if we select $v$ as the new root.

We consider the effect of making $v$ the new root. First, the height of the subtree of $v$ is still $l(v)$ . Second, since $v$ is now the new root, it could go up to its parent and then to the farthest leaf. We define this distance as $r(v)$ .

(A)
The new tree after selecting a new root is always a binary tree.
(B)
The height of the tree after making $v$ the new root is $\max(l(v), r(v))$ .
(C)
We can compute $r(v)$ for all tree nodes $v$ 's in a top-down manner. We assume that the $r$ value of $v$ 's parent in $T$ is known, so $v$ only needs to consider the $r$ value of its parent and the $l$ value of its sibling in $T$ , in order to compute its own $r$ .
(D)
The $r$ value of the root of $T$ is 1.
(E)
We can compute the $r$ values for all nodes in $O(n)$ time.

標準解析

AI 已複查