Учитывая бинарное дерево, как вы считаете все половинные узлы (у которых есть только один дочерний элемент) без использования рекурсии? Листья примечания не должны быть затронуты, поскольку они имеют обоих детей как NULL.
Input : Root of below tree
Output : 3
Nodes 7, 5 and 9 are half nodes as one of
their child is Null. So count of half nodes
in the above tree is 3
итеративный
Идея состоит в том, чтобы использовать обход уровня порядка для эффективного решения этой проблемы.
1) Create an empty Queue Node and push root node to Queue.
2) Do following while nodeQeue is not empty.
a) Pop an item from Queue and process it.
a.1) If it is half node then increment count++.
b) Push left child of popped item to Queue, if available.
c) Push right child of popped item to Queue, if available. Ниже приведена реализация этой идеи.
C ++
#include <bits/stdc++.h>
using namespace std;
struct Node
{
int data;
struct Node* left, *right;
};
unsigned int gethalfCount(struct Node* node)
{
if (!node)
return 0;
int count = 0;
queue<Node *> q;
q.push(node);
while (!q.empty())
{
struct Node *temp = q.front();
q.pop();
if (!temp->left && temp->right ||
temp->left && !temp->right)
count++;
if (temp->left != NULL)
q.push(temp->left);
if (temp->right != NULL)
q.push(temp->right);
}
return count;
}
struct Node* newNode(int data)
{
struct Node* node = new Node;
node->data = data;
node->left = node->right = NULL;
return (node);
}
int main(void)
{
struct Node *root = newNode(2);
root->left = newNode(7);
root->right = newNode(5);
root->left->right = newNode(6);
root->left->right->left = newNode(1);
root->left->right->right = newNode(11);
root->right->right = newNode(9);
root->right->right->left = newNode(4);
cout << gethalfCount(root);
return 0;
}
|
Джава
import java.util.Queue;
import java.util.LinkedList;
class Node
{
int data;
Node left, right;
public Node(int item)
{
data = item;
left = null;
right = null;
}
}
class BinaryTree
{
Node root;
int gethalfCount()
{
if (root==null)
return 0;
Queue<Node> queue = new LinkedList<Node>();
queue.add(root);
int count=0;
while (!queue.isEmpty())
{
Node temp = queue.poll();
if (temp.left!=null && temp.right==null ||
temp.left==null && temp.right!=null)
count++;
if (temp.left != null)
queue.add(temp.left);
if (temp.right != null)
queue.add(temp.right);
}
return count;
}
public static void main(String args[])
{
BinaryTree tree_level = new BinaryTree();
tree_level.root = new Node(2);
tree_level.root.left = new Node(7);
tree_level.root.right = new Node(5);
tree_level.root.left.right = new Node(6);
tree_level.root.left.right.left = new Node(1);
tree_level.root.left.right.right = new Node(11);
tree_level.root.right.right = new Node(9);
tree_level.root.right.right.left = new Node(4);
System.out.println(tree_level.gethalfCount());
}
}
|
питон
class Node:
def __init__(self ,key):
self.data = key
self.left = None
self.right = None
def gethalfCount(root):
if root is None:
return 0
queue = []
queue.append(root)
count = 0
while(len(queue) > 0):
node = queue.pop(0)
if node.left is not None and node.right is None or node.left is None and node.right is not None:
count = count+1
if node.left is not None:
queue.append(node.left)
if node.right is not None:
queue.append(node.right)
return count
root = Node(2)
root.left = Node(7)
root.right = Node(5)
root.left.right = Node(6)
root.left.right.left = Node(1)
root.left.right.right = Node(11)
root.right.right = Node(9)
root.right.right.left = Node(4)
print "%d" %(gethalfCount(root))
|
C #
using System;
using System.Collections.Generic;
public class Node
{
public int data;
public Node left, right;
public Node(int item)
{
data = item;
left = null;
right = null;
}
}
public class BinaryTree
{
Node root;
int gethalfCount()
{
if (root == null)
return 0;
Queue<Node> queue = new Queue<Node>();
queue.Enqueue(root);
int count = 0;
while (queue.Count != 0)
{
Node temp = queue.Dequeue();
if (temp.left != null && temp.right == null ||
temp.left == null && temp.right != null)
count++;
if (temp.left != null)
queue.Enqueue(temp.left);
if (temp.right != null)
queue.Enqueue(temp.right);
}
return count;
}
public static void Main()
{
BinaryTree tree_level = new BinaryTree();
tree_level.root = new Node(2);
tree_level.root.left = new Node(7);
tree_level.root.right = new Node(5);
tree_level.root.left.right = new Node(6);
tree_level.root.left.right.left = new Node(1);
tree_level.root.left.right.right = new Node(11);
tree_level.root.right.right = new Node(9);
tree_level.root.right.right.left = new Node(4);
Console.WriteLine(tree_level.gethalfCount());
}
}
|
Выход:
3
Сложность времени: O (n)
Вспомогательное пространство: O (n)
где n — количество узлов в данном двоичном дереве
рекурсивный
Идея состоит в том, чтобы пройтись по дереву в порядке заказа. Если текущий узел наполовину, мы увеличиваем результат на 1 и добавляем возвращаемые значения левого и правого поддеревьев.
C ++
#include <bits/stdc++.h>
using namespace std;
struct Node
{
int data;
struct Node* left, *right;
};
unsigned int gethalfCount(struct Node* root)
{
if (root == NULL)
return 0;
int res = 0;
if ((root->left == NULL && root->right != NULL) ||
(root->left != NULL && root->right == NULL))
res++;
res += (gethalfCount(root->left) + gethalfCount(root->right));
return res;
}
struct Node* newNode(int data)
{
struct Node* node = new Node;
node->data = data;
node->left = node->right = NULL;
return (node);
}
int main(void)
{
struct Node *root = newNode(2);
root->left = newNode(7);
root->right = newNode(5);
root->left->right = newNode(6);
root->left->right->left = newNode(1);
root->left->right->right = newNode(11);
root->right->right = newNode(9);
root->right->right->left = newNode(4);
cout << gethalfCount(root);
return 0;
}
|
Джава
import java.util.*;
class GfG {
static class Node
{
int data;
Node left, right;
}
static int gethalfCount(Node root)
{
if (root == null)
return 0;
int res = 0;
if ((root.left == null && root.right != null) ||
(root.left != null && root.right == null))
res++;
res += (gethalfCount(root.left)
+ gethalfCount(root.right));
return res;
}
static Node newNode(int data)
{
Node node = new Node();
node.data = data;
node.left = null;
node.right = null;
return (node);
}
public static void main(String[] args)
{
Node root = newNode(2);
root.left = newNode(7);
root.right = newNode(5);
root.left.right = newNode(6);
root.left.right.left = newNode(1);
root.left.right.right = newNode(11);
root.right.right = newNode(9);
root.right.right.left = newNode(4);
System.out.println(gethalfCount(root));
}
}
|
C #
using System;
class GfG
{
public class Node
{
public int data;
public Node left, right;
}
static int gethalfCount(Node root)
{
if (root == null)
return 0;
int res = 0;
if ((root.left == null && root.right != null) ||
(root.left != null && root.right == null))
res++;
res += (gethalfCount(root.left)
+ gethalfCount(root.right));
return res;
}
static Node newNode(int data)
{
Node node = new Node();
node.data = data;
node.left = null;
node.right = null;
return (node);
}
public static void Main()
{
Node root = newNode(2);
root.left = newNode(7);
root.right = newNode(5);
root.left.right = newNode(6);
root.left.right.left = newNode(1);
root.left.right.right = newNode(11);
root.right.right = newNode(9);
root.right.right.left = newNode(4);
Console.WriteLine(gethalfCount(root));
}
}
|
Выход :
3
Сложность времени: O (n)
Вспомогательное пространство: O (n)
где n — количество узлов в данном двоичном дереве
Похожие статьи:
Эта статья предоставлена г-ном Сомешем Авастхи и Ракешем Кумаром . Если вы как GeeksforGeeks и хотели бы внести свой вклад, вы также можете написать статью с помощью contribute.geeksforgeeks.org или по почте статьи contribute@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.
Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.
Рекомендуемые посты:
Подсчитать половину узлов в двоичном дереве (итеративное и рекурсивное)
0.00 (0%) 0 votes