n元树中给定节点的同级数


难度级别
经常问 亚马逊 彭博 编码国家 谷歌
N元树 队列 搜索 树遍历

问题陈述

问题“ n元树中给定节点的同级数”指出给您n元树和一个目标节点。 查找目标节点的同级数。 假定节点始终存在于树中,并且第一个节点是树的根。

使用案列

输入

n元树中给定节点的同级数

节点= 10
节点= 11

3
1

说明
10的兄弟姐妹是{41,6,32}
11的兄弟姐妹是{9}

算法

节点的同级是与给定节点处于同一级别的节点,换句话说,节点的同级比其父级的子级少一个。

考虑一下 在上面的示例中,令节点为10
10的父母= 51
51岁的孩子是{10,41,32,6}
10的兄弟姐妹是其父母的孩子,但10除外,即10的兄弟姐妹是{41,32,6}

很重要的一点:根的同级数为0。因为没有根的父级。

查找节点的同级数的想法是在给定的树上进行BFS,如果节点的子代与给定节点相同,则返回(该节点的子代数– 1)。

  1. 如果给定节点等于根或根为null,则返回0。
  2. 创建以下节点的队列 BFS 并将根推入队列。
  3. 当队列不为空时,请重复步骤4。
  4. 从队列中删除一个元素,遍历当前元素的所有子元素(如果其任何子元素等于给定节点),返回(当前节点的子元素数– 1),否则将这些子元素推入队列。
  5. 如果没有与给定节点匹配的节点,则返回-1。

代码

Java代码在n元树中查找给定节点的同级数

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

class NumberOfSiblingsOfAGivenNodeInNAryTree {
    // class representing node of n-ary tree
    static class Node {
        
        ArrayList<Node> child;
        int data;
        public Node(int data) {
            this.data = data;
            this.child = new ArrayList<>();
        }
    }

    private static int siblings(Node root, int target) {
        // if the given node is equals to the root or root is null, return 0
        if (root == null || root.data == target) {
            return 0;
        }

        // create a queue of nodes
        Queue<Node> queue = new LinkedList<>();
        // push the root to queue
        queue.add(root);

        // do a BFS of the tree
        while (!queue.isEmpty()) {
            // remove one element from the queue
            Node curr = queue.poll();
            // traverse its children
            for (int i = 0; i < curr.child.size(); i++) {
                // current child
                Node currChild = curr.child.get(i);
                // if current child is the target, return (parent's children count - 1)
                if (currChild.data == target) {
                    return (curr.child.size() - 1);
                }
                // add the child to the queue
                queue.add(currChild);
            }
        }

        // if there is no match, return -1
        return -1;
    }

    public static void main(String[] args) {
        // Example n-ary tree
        Node root = new Node(51);
        // children of 51
        root.child.add(new Node(10));
        root.child.add(new Node(41));
        root.child.add(new Node(6));
        root.child.add(new Node(32));
        // children of 10
        root.child.get(0).child.add(new Node(53));
        // children of 41
        root.child.get(1).child.add(new Node(95));
        // children of 6
        root.child.get(2).child.add(new Node(28));
        // children of 32
        root.child.get(3).child.add(new Node(9));
        root.child.get(3).child.add(new Node(11));
        // children of 53
        root.child.get(0).child.get(0).child.add(new Node(5));
        root.child.get(0).child.get(0).child.add(new Node(7));
        // children of 11
        root.child.get(3).child.get(1).child.add(new Node(3));
        root.child.get(3).child.get(1).child.add(new Node(8));

        System.out.println(siblings(root, 10));
        System.out.println(siblings(root, 11));
    }
}
3
1

C ++代码在n元树中查找给定节点的同级数

#include <bits/stdc++.h> 
using namespace std; 

// class representing node of a n-ary tree
class Node {
    public:
    int data;
    vector<Node*> child;
    
    Node(int d) {
        data = d;
    }
};

int siblings(Node *root, int target) {
    // if the given node is equals to the root or root is null, return 0
    if (root == NULL || root->data == target) {
        return 0;
    }
    
    // create a queue of nodes
    queue<Node*> q;
    // push the root to queue
    q.push(root);
    
    // do a BFS of the tree
    while (!q.empty()) {
        // remove one element from the queue
        Node *curr = q.front();
        q.pop();
        // traverse its children
        for (int i = 0; i < curr->child.size(); i++) {
            // current child
            Node *currChild = curr->child[i];
            // if current child is the target, return (parent's children count - 1)
            if (currChild->data == target) {
                return (curr->child.size() - 1);
            }
            // add the child to the queue
            q.push(curr->child[i]);
        }
    }
    
    // if there is no match, return -1
    return -1;
}

int main() {
    // Example n-ary tree
    Node *root = new Node(51);
    // children of 51
    root->child.push_back(new Node(10));
    root->child.push_back(new Node(41));
    root->child.push_back(new Node(6));
    root->child.push_back(new Node(32));
    // children of 10
    root->child[0]->child.push_back(new Node(53));
    // children of 41
    root->child[1]->child.push_back(new Node(95));
    // children of 6
    root->child[2]->child.push_back(new Node(28));
    // children of 32
    root->child[3]->child.push_back(new Node(9));
    root->child[3]->child.push_back(new Node(11));
    // children of 53
    root->child[0]->child[0]->child.push_back(new Node(5));
    root->child[0]->child[0]->child.push_back(new Node(7));
    // children of 11
    root->child[3]->child[1]->child.push_back(new Node(3));
    root->child[3]->child[1]->child.push_back(new Node(8));

    cout<<siblings(root, 10)<<endl;
    cout<<siblings(root, 11)<<endl;
    
    return 0;
}
3
1

复杂度分析

时间复杂度

上), 因为我们已经为树完成了BFS。 我们刚刚遍历了所有使算法在线性时间内运行的节点。

空间复杂度

上), 为BFS使用队列已使我们失去了线性空间。 因此,该算法的空间复杂度为O(N)。