# 50028. Subtrees

## Problem Description

Given the address of the root of a binary tree, where each node has an integer label, and an integer $k$, find all nodes (denoted as $n$) that satisfy the following properties.

• The label of $n$ is not $k$.
• There is at least one node of label $k$ in the left subtree of $n$.
• There is at least one node of label $k$ in the right subtree of $n$.

p10070

### subtree.h

1234567891011#ifndef _SUBTREE_H#define _SUBTREE_H typedef struct Node {    int label;    struct Node *left, *right;} Node; int getNode(Node *root, int label[], int k); #endif


Please place the labels you found in the label array (in any order), and retrun the number of nodes found as the return value.

• 5pt. There are exactly three nodes in the binary tree, and all of them have label $k$.
• 15pt. There are exactly three nodes in the binary tree, and exactly two of them have label $k$.
• 40pt. The number of nodes is no more than 50.
• 40pt. The number of nodes is no more than 10000.

## Hint

The problem is easy once you know how to compute the number of nodes with label $k$ in every subtree recursively.

## main.c (test)

1234567891011121314151617181920212223242526272829303132333435#include "subtree.h"#include <stdio.h>#include <stdlib.h>#include <assert.h> Node* newNode(int label, Node *l, Node *r) {    Node *u = (Node *) malloc(sizeof(Node));    u->label = label, u->left = l, u->right = r;    return u;} int main() {    Node *root = newNode(        10,            newNode(                5,                    newNode(1, NULL, NULL),                    newNode(1, NULL, NULL)                            ),            newNode(                7,                    newNode(1, NULL, NULL),                    newNode(5, NULL, NULL)                            )    );    int k;    while (scanf("%d", &k) == 1) {        int A[128];        int n = getNode(root, A, k);        printf("%d\n", n);        for (int i = 0; i < n; i++)            printf("%d%c", A[i], i == n-1 ? '\n' : ' ');    }    return 0;}


## Sample Input

15


## Sample Output

25 10110


## Hint 2

$\mathcal{O}(N^2)$ 無法通過所有測資。請使用一次 traversal 在 $\mathcal{O}(N)$ 計算答案。