原文:
给定二叉树，打印所有没有兄弟节点的节点(兄弟节点是具有相同父节点的节点。在二叉树中，最多只能有一个兄弟)。不应打印根目录，因为根目录不能有同级。 例如，对于下面的树，输出应该是“4 5 6”。
这是一个典型的树遍历问题。我们从根开始，检查该节点是否有一个子节点，如果有，则打印该节点的唯一子节点。如果节点有两个子节点，则这两个子节点都重复出现。
下面是上述方法的实现:
c
/* program to find singles in a given binary tree */
#include
using namespace std;
// a binary tree node
struct node
{
struct node *left, *right;
int key;
};
// utility function to create a new tree node
node* newnode(int key)
{
node *temp = new node;
temp->key = key;
temp->left = temp->right = null;
return temp;
}
// function to print all non-root nodes
// that don't have a sibling
void printsingles(struct node *root)
{
// base case
if (root == null)
return;
// if this is an internal node, recur for left
// and right subtrees
if (root->left != null && root->right != null)
{
printsingles(root->left);
printsingles(root->right);
}
// if left child is null and right is not,
// print right child
// and recur for right child
else if (root->right != null)
{
cout << root->right->key << " ";
printsingles(root->right);
}
// if right child is null and left is
// not, print left child
// and recur for left child
else if (root->left != null)
{
cout << root->left->key << " ";
printsingles(root->left);
}
}
// driver program to test above functions
int main()
{
// let us create binary tree
// given in the above example
node *root = newnode(1);
root->left = newnode(2);
root->right = newnode(3);
root->left->right = newnode(4);
root->right->left = newnode(5);
root->right->left->left = newnode(6);
printsingles(root);
return 0;
}
java 语言(一种计算机语言，尤用于创建网站)
// java program to print all nodes
// that don't have sibling
// a binary tree node
class node
{
int data;
node left, right;
node(int item)
{
data = item;
left = right = null;
}
}
class binarytree
{
node root;
// function to print all non-root nodes
// that don't have a sibling
void printsingles(node node)
{
// base case
if (node == null)
return;
// if this is an internal node, recur for left
// and right subtrees
if (node.left != null && node.right != null)
{
printsingles(node.left);
printsingles(node.right);
}
// if left child is null and right
// is not, print right child
// and recur for right child
else if (node.right != null)
{
system.out.print(node.right.data " ");
printsingles(node.right);
}
// if right child is null and left
// is not, print left child
// and recur for left child
else if (node.left != null)
{
system.out.print( node.left.data " ");
printsingles(node.left);
}
}
// driver program to test the above functions
public static void main(string args[])
{
binarytree tree = new binarytree();
/* let us construct the tree
shown in above diagram */
tree.root = new node(1);
tree.root.left = new node(2);
tree.root.right = new node(3);
tree.root.left.right = new node(4);
tree.root.right.left = new node(5);
tree.root.right.left.right = new node(6);
tree.printsingles(tree.root);
}
}
// this code has been contributed by mayank jaiswal
计算机编程语言
# python3 program to find singles in a given binary tree
# a binary tree node
class node:
# a constructor to create new tree node
def __init__(self, key):
self.key = key
self.left = none
self.right = none
# function to print all non-root nodes that don't have
# a sibling
def printsingles(root):
# base case
if root is none:
return
# if this is an internal node , recur for left
# and right subtrees
if root.left is not none and root.right is not none:
printsingles(root.left)
printsingles(root.right)
# if left child is null, and right is not, print
# right child and recur for right child
elif root.right is not none:
print root.right.key,
printsingles(root.right)
# if right child is null and left is not, print
# left child and recur for left child
elif root.left is not none:
print root.left.key,
printsingles(root.left)
# driver program to test above function
root = node(1)
root.left = node(2)
root.right = node(3)
root.left.right = node(4)
root.right.left = node(5)
root.right.left.left = node(6)
printsingles(root)
# this code is contributed by nikhil kumar singh(nickzuck_007)
c
using system;
// c# program to print all nodes that don't have sibling
// a binary tree node
public class node
{
public int data;
public node left, right;
public node(int item)
{
data = item;
left = right = null;
}
}
public class binarytree
{
public node root;
// function to print all non-root nodes that don't have a sibling
public virtual void printsingles(node node)
{
// base case
if (node == null)
{
return;
}
// if this is an internal node, recur for left
// and right subtrees
if (node.left != null && node.right != null)
{
printsingles(node.left);
printsingles(node.right);
}
// if left child is null and right is not, print right child
// and recur for right child
else if (node.right != null)
{
console.write(node.right.data " ");
printsingles(node.right);
}
// if right child is null and left is not, print left child
// and recur for left child
else if (node.left != null)
{
console.write(node.left.data " ");
printsingles(node.left);
}
}
// driver program to test the above functions
public static void main(string[] args)
{
binarytree tree = new binarytree();
/* let us construct the tree shown in above diagram */
tree.root = new node(1);
tree.root.left = new node(2);
tree.root.right = new node(3);
tree.root.left.right = new node(4);
tree.root.right.left = new node(5);
tree.root.right.left.right = new node(6);
tree.printsingles(tree.root);
}
}
// this code is contributed by shrikant13
java 描述语言
输出:
4 5 6
时间复杂度: o(n)
在中交替实现迭代方法:
我们从根开始，检查该节点是否有一个子节点，如果有，则打印该节点的唯一子节点。如果该节点有两个子节点，则推送队列中的两个子节点。
下面是上述方法的实现:
c 14
// cpp program for above approach
#include
using namespace std;
// a binary tree node
struct node
{
struct node *left, *right;
int data;
};
// utility function to
// create a new tree node
node* newnode(int key)
{
node *temp = new node;
temp->data= key;
temp->left = temp->right = null;
return temp;
}
// function to print all
// non-root nodes that
// don't have a sibling
void printsingles(struct node *root)
{
// base case
if (root == null)
return;
queue q1;
q1.push(root);
int flag=0;
vector v;
// while q1 is not empty
while(q1.empty() == false)
{
struct node * temp=q1.front();
q1.pop();
// check if temp->left is not
// null and temp->right is null
if(temp->left != null &&
temp->right == null)
{
flag=1;
v.push_back(temp->left->data);
}
// check if temp->left is equal
// null and temp->right is not null
if(temp->left == null &&
temp->right != null)
{
flag=1;
v.push_back(temp->right->data);
}
// check if temp->left is not
// null
if(temp->left != null)
{
q1.push(temp->left);
}
// check if temp->right is not
// null
if(temp->right != null)
{
q1.push(temp->right);
}
}
// sort v in increasing order
sort(v.begin(), v.end());
// iterate i from 0 to v.size() - 1
for (int i = 0; i < v.size(); i )
{
cout<< v[i] << " ";
}
// check is v is empty
if (v.size() == 0)
{
cout<<"-1";
}
}
// driver program to test
// above functions
int main()
{
// let us create binary tree
// given in the above example
node *root = newnode(1);
root->left = newnode(2);
root->right = newnode(3);
root->left->right = newnode(4);
root->right->left = newnode(5);
root->right->left->left = newnode(6);
// function call
printsingles(root);
return 0;
}
java 语言(一种计算机语言，尤用于创建网站)
// java program for above approach
import java.util.*;
class gfg
{
// a binary tree node
static class node
{
node left, right;
int data;
};
// utility function to
// create a new tree node
static node newnode(int key)
{
node temp = new node();
temp.data = key;
temp.left = temp.right = null;
return temp;
}
// function to print all
// non-root nodes that
// don't have a sibling
static void printsingles(node root)
{
// base case
if (root == null)
return;
queue q1 = new linkedlist<>();
q1.add(root);
int flag = 0;
vector v = new vector<>();
// while q1 is not empty
while(q1.isempty() == false)
{
node temp = q1.peek();
q1.remove();
// check if temp.left is not
// null and temp.right is null
if(temp.left != null &&
temp.right == null)
{
flag = 1;
v.add(temp.left.data);
}
// check if temp.left is equal
// null and temp.right is not null
if(temp.left == null &&
temp.right != null)
{
flag = 1;
v.add(temp.right.data);
}
// check if temp.left is not
// null
if(temp.left != null)
{
q1.add(temp.left);
}
// check if temp.right is not
// null
if(temp.right != null)
{
q1.add(temp.right);
}
}
// sort v in increasing order
collections.sort(v);
// iterate i from 0 to v.size() - 1
for (int i = 0; i < v.size(); i )
{
system.out.print( v.get(i) " ");
}
// check is v is empty
if (v.size() == 0)
{
system.out.print("-1");
}
}
// driver program to test
// above functions
public static void main(string[] args)
{
// let us create binary tree
// given in the above example
node root = newnode(1);
root.left = newnode(2);
root.right = newnode(3);
root.left.right = newnode(4);
root.right.left = newnode(5);
root.right.left.left = newnode(6);
// function call
printsingles(root);
}
}
// this code is contributed by aashish1995
python 3
# python3 program for above approach
from queue import queue
# a binary tree node
class node:
# a constructor to create new tree node
def __init__(self, key):
self.key = key
self.left = none
self.right = none
# function to print all non-root nodes
# that don't have a sibling
def printsingles(root):
# base case
if root is none:
return
q1 = queue(maxsize = 100)
q1.put(root)
flag = 0
v = []
# while q1 is not empty
while q1.empty() == false:
temp = q1.get()
# check if temp->left is not
# null and temp->right is null
if temp.left is not none and temp.right is none:
flag = 1
v.append(temp.left.key)
# check if temp->left is equal
# null and temp->right is not null
if temp.left is none and temp.right is not none:
flag = 1
v.append(temp.right.key)
# check if temp->left is not
# null
if temp.left is not none:
q1.put(temp.left)
# check if temp->right is not
# null
if temp.right is not none:
q1.put(temp.right)
# sort v in increasing order
v.sort()
for i in v:
print(i, end = " ")
# check is v is empty
if len(v) == 0:
print("-1")
# driver code
root = node(1)
root.left = node(2)
root.right = node(3)
root.left.right = node(4)
root.right.left = node(5)
root.right.left.left = node(6)
printsingles(root)
# this code is contributed by codersaty
c
// c# program for above approach
using system;
using system.collections.generic;
class gfg
{
// a binary tree node
public
class node
{
public
node left, right;
public
int data;
};
// utility function to
// create a new tree node
static node newnode(int key)
{
node temp = new node();
temp.data = key;
temp.left = temp.right = null;
return temp;
}
// function to print all
// non-root nodes that
// don't have a sibling
static void printsingles(node root)
{
// base case
if (root == null)
return;
queue q1 = new queue();
q1.enqueue(root);
int flag = 0;
list v = new list();
// while q1 is not empty
while(q1.count != 0)
{
node temp = q1.peek();
q1.dequeue();
// check if temp.left is not
// null and temp.right is null
if(temp.left != null &&
temp.right == null)
{
flag = 1;
v.add(temp.left.data);
}
// check if temp.left is equal
// null and temp.right is not null
if(temp.left == null &&
temp.right != null)
{
flag = 1;
v.add(temp.right.data);
}
// check if temp.left is not
// null
if(temp.left != null)
{
q1.enqueue(temp.left);
}
// check if temp.right is not
// null
if(temp.right != null)
{
q1.enqueue(temp.right);
}
}
// sort v in increasing order
v.sort();
// iterate i from 0 to v.count - 1
for (int i = 0; i < v.count; i )
{
console.write( v[i] " ");
}
// check is v is empty
if (v.count == 0)
{
console.write("-1");
}
}
// driver program to test
// above functions
public static void main(string[] args)
{
// let us create binary tree
// given in the above example
node root = newnode(1);
root.left = newnode(2);
root.right = newnode(3);
root.left.right = newnode(4);
root.right.left = newnode(5);
root.right.left.left = newnode(6);
// function call
printsingles(root);
}
}
// this code is contributed by rajput-ji.
java 描述语言
output
4 5 6
本文由阿曼古普塔整理。如果您发现任何不正确的地方，或者您想分享关于上面讨论的主题的更多信息，请写评论
麻将胡了pg电子网站的版权属于：月萌api www.moonapi.com，转载请注明出处
