原文:
给定一个二叉树，任务是打印所有恰好有一个子节点的节点。如果不存在这样的节点，则打印“-1”。 例:
input:
2
/ \
3 5
/ / \
7 8 6
output: 3
explanation:
there is only one node having
single child that is 3.
input:
9
/ \
7 8
/ \
4 3
output: -1
explanation:
there is no node having exactly one
child in the binary tree.
方法:想法是在，并且在遍历的每一步检查节点是否正好有一个子节点。然后将该节点追加到结果数组中，以跟踪这些节点。遍历之后，只需打印这个结果数组的每个元素。
下面是上述方法的实现:
c
// c implementation to print
// the nodes having a single child
#include
using namespace std;
// class of the binary tree node
struct node
{
int data;
node *left, *right;
node(int x)
{
data = x;
left = right = null;
}
};
vector lst;
// function to find the nodes
// having single child
void printnodesonechild(node* root)
{
// base case
if (root == null)
return;
// condition to check if the
// node is having only one child
if (root->left != null &&
root->right == null ||
root->left == null &&
root->right != null)
{
lst.push_back(root->data);
}
// traversing the left child
printnodesonechild(root -> left);
// traversing the right child
printnodesonechild(root -> right);
}
//driver code
int main()
{
// constructing the binary tree
node *root = new node(2);
root -> left = new node(3);
root -> right = new node(5);
root -> left -> left = new node(7);
root -> right -> left = new node(8);
root -> right -> right = new node(6);
// function calling
printnodesonechild(root);
// condition to check if there is
// no such node having single child
if (lst.size() == 0)
printf("-1");
else
{
for(int value : lst)
{
cout << (value) << endl;
}
}
}
// this code is contributed by mohit kumar 29
java 语言(一种计算机语言，尤用于创建网站)
// java implementation to print
// the nodes having a single child
import java.util.vector;
// class of the binary tree node
class node
{
int data;
node left, right;
node(int data)
{
this.data = data;
}
}
class gfg{
// list to keep track of nodes
// having single child
static vector list = new vector<>();
// function to find the nodes
// having single child
static void printnodesonechild(node root)
{
// base case
if (root == null)
return;
// condition to check if the node
// is having only one child
if (root.left != null && root.right == null ||
root.left == null && root.right != null)
{
list.add(root.data);
}
// traversing the left child
printnodesonechild(root.left);
// traversing the right child
printnodesonechild(root.right);
}
// driver code
public static void main(string[] args)
{
// constructing the binary tree
node root = new node(2);
root.left = new node(3);
root.right = new node(5);
root.left.left = new node(7);
root.right.left = new node(8);
root.right.right = new node(6);
// function calling
printnodesonechild(root);
// condition to check if there is
// no such node having single child
if (list.size() == 0)
system.out.println(-1);
else
{
for(int value : list)
{
system.out.println(value);
}
}
}
}
// this code is contributed by sumit_9
python 3
# python3 implementation to print
# the nodes having a single child
# class of the binary tree node
class node:
# constructor to construct
# the node of the binary tree
def __init__(self, val):
self.val = val
self.left = none
self.right = none
# list to keep track of
# nodes having single child
single_child_nodes = []
# function to find the nodes
# having single child
def printnodesonechild(root):
# base case
if not root:
return
# condition to check if the node
# is having only one child
if not root.left and root.right:
single_child_nodes.append(root)
elif root.left and not root.right:
single_child_nodes.append(root)
# traversing the left child
printnodesonechild(root.left)
# traversing the right child
printnodesonechild(root.right)
return
# driver code
if __name__ == "__main__":
# condtruction of binary tree
root = node(2)
root.left = node(3)
root.right = node(5)
root.left.left = node(7)
root.right.left = node(8)
root.right.right = node(6)
# function call
printnodesonechild(root)
# condition to check if there is
# no such node having single child
if not len(single_child_nodes):
print(-1)
else:
for i in single_child_nodes:
print(i.val, end = " ")
print()
c
// c# implementation to print
// the nodes having a single child
using system;
using system.collections;
class gfg{
// structure of binary tree
public class node
{
public node left;
public node right;
public int data;
};
// function to create a new node
static node newnode(int key)
{
node node = new node();
node.left = node.right = null;
node.data = key;
return node;
}
// list to keep track of nodes
// having single child
static arraylist list = new arraylist();
// function to find the nodes
// having single child
static void printnodesonechild(node root)
{
// base case
if (root == null)
return;
// condition to check if the node
// is having only one child
if (root.left != null && root.right == null ||
root.left == null && root.right != null)
{
list.add(root.data);
}
// traversing the left child
printnodesonechild(root.left);
// traversing the right child
printnodesonechild(root.right);
}
// driver code
static public void main()
{
// constructing the binary tree
node root = newnode(2);
root.left = newnode(3);
root.right = newnode(5);
root.left.left = newnode(7);
root.right.left = newnode(8);
root.right.right = newnode(6);
// function calling
printnodesonechild(root);
// condition to check if there is
// no such node having single child
if (list.count == 0)
console.writeline(-1);
else
{
foreach(int value in list)
{
console.writeline(value);
}
}
}
}
// this code is contributed by offbeat
java 描述语言
output
3
麻将胡了pg电子网站的版权属于：月萌api www.moonapi.com，转载请注明出处
