-->
当前位置:首页 > 题库

PROGRAMMING:The nearest common ancestor problem of Sequential Binary Trees

Luz5年前 (2021-05-10)题库409
Suppose that there are two nodes named $$I $$and $$J $$in the binary tree stored in sequence, please design an algorithm to find out the number and value of their nearest common ancestor node.
###Input format:
Enter the first line to give the positive integer $$n $$($$Le 1000 $$), that is, the maximum capacity of sequential storage; Line 2 gives $$n $$non negative integers separated by spaces. Where 0 represents the empty node in the binary tree (if the first node is 0, it represents an empty tree); Line 3 gives a pair of node numbers $$I $$and $$J $$.
The title ensures that the input corresponds to a binary tree correctly, and $$1, J, n $$.
###Output format:
If the corresponding node of $$I $$or $$J $$is empty, output 'error: T [x] is null', where 'x' is the number of the first error found in $$I $$or $$J $$; Otherwise, output the number and value of the nearest common ancestor node of the two nodes numbered $$I $$and $$J $$in one line, separated by a space.
###Input sample 1:
```in
fifteen
4 3 5 1 10 0 7 0 2 0 9 0 0 6 8
11 4
```
###Output sample 1:
```out
2 3
```
###Input example 2:
```
fifteen
4 3 5 1 0 0 7 0 2 0 9 0 0 6 8
12 8
```
###Output example 2:
```
ERROR: T[12] is NULL
```






answer:If there is no answer, please comment