𝓣𝓱𝓮 𝓮𝓿𝓮𝓷𝓲𝓷𝓰 𝓫𝓻𝓮𝓮𝔃𝓮 𝓪𝓵𝓶𝓸𝓼𝓽 𝓭𝓻𝓲𝓮𝓼 𝓽𝓱𝓮 𝓮𝓷𝓽𝓲𝓻𝓮 𝓪𝓵𝓵𝓮𝔂, 𝓽𝓱𝓮 𝓫𝓾𝓻𝓷𝓽-𝓸𝓾𝓽 𝓵𝓲𝓰𝓱𝓽𝓼 𝓬𝓪𝓷 𝓷𝓸 𝓵𝓸𝓷𝓰𝓮𝓻 𝓲𝓵𝓵𝓾𝓶𝓲𝓷𝓪𝓽𝓮 𝓾𝓼.
--- 𝓔𝓿𝓮𝓷𝓲𝓷𝓰 𝓑𝓻𝓮𝓮𝔃𝓮

𝓑𝓪𝓬𝓴𝓰𝓻𝓸𝓾𝓷𝓭

$YYD$ 𝓲𝓼 𝓪 𝓿𝓮𝓻𝔂 𝓼𝓶𝓪𝓻𝓽 𝓹𝓮𝓻𝓼𝓸𝓷. 𝓡𝓮𝓬𝓮𝓷𝓽𝓵𝔂, 𝓼𝓱𝓮 𝓬𝓪𝓶𝓮 𝓾𝓹 𝔀𝓲𝓽𝓱 𝓪 𝓹𝓻𝓸𝓫𝓵𝓮𝓶 𝓽𝓸 𝓮𝔁𝓮𝓻𝓬𝓲𝓼𝓮 𝓱𝓮𝓻 𝓫𝓻𝓪𝓲𝓷, 𝓫𝓾𝓽 𝓼𝓱𝓮 𝓯𝓲𝓷𝓭𝓼 𝓲𝓽 𝓪 𝓫𝓲𝓽 𝓬𝓱𝓪𝓵𝓵𝓮𝓷𝓰𝓲𝓷𝓰, 𝓼𝓸 𝓼𝓱𝓮 𝓲𝓼 𝓪𝓼𝓴𝓲𝓷𝓰 𝓯𝓸𝓻 𝔂𝓸𝓾𝓻 𝓱𝓮𝓵𝓹.

𝓟𝓻𝓸𝓫𝓵𝓮𝓶 𝓓𝓮𝓼𝓬𝓻𝓲𝓹𝓽𝓲𝓸𝓷

𝓣𝓱𝓮 𝓹𝓼𝓮𝓾𝓭𝓸𝓬𝓸𝓭𝓮 𝓯𝓸𝓻 𝓭𝓮𝓽𝓮𝓻𝓶𝓲𝓷𝓲𝓷𝓰 𝔀𝓱𝓮𝓽𝓱𝓮𝓻 𝓽𝔀𝓸 𝓽𝓻𝓮𝓮𝓼 𝓪𝓻𝓮 𝓲𝓼𝓸𝓶𝓸𝓻𝓹𝓱𝓲𝓬 𝓲𝓼 𝓼𝓱𝓸𝔀𝓷 𝓫𝓮𝓵𝓸𝔀. 𝓟𝓵𝓮𝓪𝓼𝓮 𝓱𝓮𝓵𝓹 𝓨𝓨𝓓 𝓬𝓪𝓵𝓬𝓾𝓵𝓪𝓽𝓮 𝓽𝓱𝓮 𝓮𝔁𝓹𝓮𝓬𝓽𝓮𝓭 𝓷𝓾𝓶𝓫𝓮𝓻 𝓸𝓯 𝓵𝓮𝓪𝓯 𝓷𝓸𝓭𝓮𝓼 𝓲𝓷 𝓪 𝓻𝓸𝓸𝓽𝓮𝓭 𝓽𝓻𝓮𝓮.

$$\def\arraystretch{1.2} \begin{array}{ll} \hline \textbf{Algorithm 1}&\text{Check}(T1,T2) \\ \hline 1&\textbf{Require: }\text{ Nodes of two trees } T1, T2 \\ 2&\qquad\textbf{if}\ T1 = \text{null} \textbf{ or } T2 = \text{null} \textbf{ then } \\ 3&\qquad\qquad\textbf{return}\ T1 = \text{null} \textbf{ and } T2 = \text{null} \\ 4&\qquad\textbf{else} \\ 5&\qquad\qquad\textbf{if}\ T1 \rightarrow \mathit{value} \neq T2 \rightarrow \mathit{value} \textbf{ then } \\ 6&\qquad\qquad\qquad\textbf{return}\ \textbf{false} \\ 7&\qquad\qquad\textbf{endif} \\ 8&\qquad\qquad\textbf{return}\ \text{Check}(T1 \rightarrow \mathit{leftson}, T2 \rightarrow \mathit{leftson}) \\ &\qquad\qquad\qquad\textbf{ and } \text{Check}(T1 \rightarrow \mathit{rightson}, T2 \rightarrow \mathit{rightson}) \\ 9&\qquad\textbf{endif} \\ \hline \end{array}$$

𝓘𝓷𝓹𝓾𝓽 𝓕𝓸𝓻𝓶𝓪𝓽

• 𝓘𝓷𝓹𝓾𝓽 𝓪 𝓹𝓸𝓼𝓲𝓽𝓲𝓿𝓮 𝓲𝓷𝓽𝓮𝓰𝓮𝓻 $n$, 𝓻𝓮𝓹𝓻𝓮𝓼𝓮𝓷𝓽𝓲𝓷𝓰 𝓽𝓱𝓮 𝓷𝓾𝓶𝓫𝓮𝓻 𝓸𝓯 𝓷𝓸𝓭𝓮𝓼 𝓲𝓷 𝓽𝓱𝓮 𝓻𝓸𝓸𝓽𝓮𝓭 𝓽𝓻𝓮𝓮.

𝓞𝓾𝓽𝓹𝓾𝓽 𝓕𝓸𝓻𝓶𝓪𝓽

• 𝓞𝓾𝓽𝓹𝓾𝓽 𝓽𝓱𝓮 𝓮𝔁𝓹𝓮𝓬𝓽𝓮𝓭 𝓷𝓾𝓶𝓫𝓮𝓻 𝓸𝓯 𝓵𝓮𝓪𝓯 𝓷𝓸𝓭𝓮𝓼 𝓲𝓷 𝓽𝓱𝓮 𝓽𝓻𝓮𝓮.

Sample #1

Sample Input #1

1

Sample Output #1

1.000000000

Sample #2

Sample Input #2

3

Sample Output #2

1.200000000

𝓗𝓲𝓷𝓽𝓼

𝓓𝓪𝓽𝓪 𝓒𝓸𝓷𝓼𝓽𝓻𝓪𝓲𝓷𝓽𝓼

𝓕𝓸𝓻 30% 𝓸𝓯 𝓽𝓱𝓮 𝓭𝓪𝓽𝓪, $1 \le n \le 10$.

𝓕𝓸𝓻 70% 𝓸𝓯 𝓽𝓱𝓮 𝓭𝓪𝓽𝓪, $1 \le n \le 100$.

𝓕𝓸𝓻 100% 𝓸𝓯 𝓽𝓱𝓮 𝓭𝓪𝓽𝓪, $1 \le n \le 10^9$.