原文:
给定一个二叉树,任务是打印有孙子的节点。
示例:
输入:
输出: 20 8 说明: 20 和 8 是 4、12 和 10、14 的祖辈。
输入:
输出: 1 说明: 1 是 4、5 的祖父母。
方法:思路采用。以下是步骤:
- 在每个节点遍历给定的树。
- 检查每个节点是否有子节点。
- 对于任何树节点(比如 temp ),如果下面的节点之一存在,那么当前节点就是祖父节点:
- temp->左侧->左侧。
- temp->左->右。
- temp->右->左。
- temp->right->right。
- 如果任何节点 temp 存在上述任何一种情况,则节点 temp 是祖父母节点。
下面是上述方法的实现:
c
// c program for the above approach
#include
using namespace std;
// a binary tree node
struct node {
struct node *left, *right;
int key;
};
// function to create new tree node
node* newnode(int key)
{
node* temp = new node;
temp->key = key;
temp->left = temp->right = null;
return temp;
}
// function to print the nodes of
// the binary tree having a grandchild
void cal(struct node* root)
{
// base case to check
// if the tree exists
if (root == null)
return;
else {
// check if there is a left and
// right child of the curr node
if (root->left != null
&& root->right != null) {
// check for grandchildren
if (root->left->left != null
|| root->left->right != null
|| root->right->left != null
|| root->right->right != null) {
// print the node's key
cout << root->key << " ";
}
}
// check if the left child
// of node is not null
else if (root->left != null) {
// check for grandchildren
if (root->left->left != null
|| root->left->right != null) {
cout << root->key << " ";
}
}
// check if the right child
// of node is not null
else if (root->right != null) {
// check for grandchildren
if (root->right->left != null
|| root->right->right != null) {
cout << root->key << " ";
}
}
// recursive call on left and
// right subtree
cal(root->left);
cal(root->right);
}
}
// driver code
int main()
{
// given tree
struct node* root = newnode(1);
root->left = newnode(2);
root->right = newnode(3);
root->left->left = newnode(4);
root->left->right = newnode(5);
// function call
cal(root);
return 0;
}
java 语言(一种计算机语言,尤用于创建网站)
// java program for the above approach
import java.util.*;
class gfg{
// a binary tree node
static class node
{
node left, right;
int key;
};
// function to create new tree node
static node newnode(int key)
{
node temp = new node();
temp.key = key;
temp.left = temp.right = null;
return temp;
}
// function to print the nodes of
// the binary tree having a grandchild
static void cal(node root)
{
// base case to check
// if the tree exists
if (root == null)
return;
else
{
// check if there is a left and
// right child of the curr node
if (root.left != null &&
root.right != null)
{
// check for grandchildren
if (root.left.left != null ||
root.left.right != null ||
root.right.left != null ||
root.right.right != null)
{
// print the node's key
system.out.print(root.key " ");
}
}
// check if the left child
// of node is not null
else if (root.left != null)
{
// check for grandchildren
if (root.left.left != null ||
root.left.right != null)
{
system.out.print(root.key " ");
}
}
// check if the right child
// of node is not null
else if (root.right != null)
{
// check for grandchildren
if (root.right.left != null ||
root.right.right != null)
{
system.out.print(root.key " ");
}
}
// recursive call on left and
// right subtree
cal(root.left);
cal(root.right);
}
}
// driver code
public static void main(string[] args)
{
// given tree
node root = newnode(1);
root.left = newnode(2);
root.right = newnode(3);
root.left.left = newnode(4);
root.left.right = newnode(5);
// function call
cal(root);
}
}
// this code is contributed by amit katiyar
python 3
# python3 program for the
# above approach
# a binary tree node
class newnode:
def __init__(self, key):
self.key = key
self.left = none
self.right = none
# function to print the nodes
# of the binary tree having a
# grandchild
def cal(root):
# base case to check
# if the tree exists
if (root == none):
return
else:
# check if there is a left
# and right child of the
# curr node
if (root.left != none and
root.right != none):
# check for grandchildren
if (root.left.left != none or
root.left.right != none or
root.right.left != none or
root.right.right != none):
# print the node's key
print(root.key, end = " ")
# check if the left child
# of node is not none
elif (root.left != none):
# check for grandchildren
if (root.left.left != none or
root.left.right != none):
print(root.key, end = " ")
# check if the right child
# of node is not none
elif(root.right != none):
# check for grandchildren
if (root.right.left != none or
root.right.right != none):
print(root.key, end = " ")
# recursive call on left and
# right subtree
cal(root.left)
cal(root.right)
# driver code
if __name__ == '__main__':
# given tree
root = newnode(1)
root.left = newnode(2)
root.right = newnode(3)
root.left.left = newnode(4)
root.left.right = newnode(5)
# function call
cal(root)
# this code is contributed by surendra_gangwar
c
// c# program for the
// above approach
using system;
class gfg{
// a binary tree node
public class node
{
public node left, right;
public int key;
};
// function to create new
// tree node
static node newnode(int key)
{
node temp = new node();
temp.key = key;
temp.left = temp.right = null;
return temp;
}
// function to print the
// nodes of the binary tree
// having a grandchild
static void cal(node root)
{
// base case to check
// if the tree exists
if (root == null)
return;
else
{
// check if there is a left and
// right child of the curr node
if (root.left != null &&
root.right != null)
{
// check for grandchildren
if (root.left.left != null ||
root.left.right != null ||
root.right.left != null ||
root.right.right != null)
{
// print the node's key
console.write(root.key " ");
}
}
// check if the left child
// of node is not null
else if (root.left != null)
{
// check for grandchildren
if (root.left.left != null ||
root.left.right != null)
{
console.write(root.key " ");
}
}
// check if the right child
// of node is not null
else if (root.right != null)
{
// check for grandchildren
if (root.right.left != null ||
root.right.right != null)
{
console.write(root.key " ");
}
}
// recursive call on left and
// right subtree
cal(root.left);
cal(root.right);
}
}
// driver code
public static void main(string[] args)
{
// given tree
node root = newnode(1);
root.left = newnode(2);
root.right = newnode(3);
root.left.left = newnode(4);
root.left.right = newnode(5);
// function call
cal(root);
}
}
// this code is contributed by princi singh
java 描述语言
output:
1
时间复杂度: o(n) ,其中 n 为节点数。 辅助空间: o(n)
麻将胡了pg电子网站的版权属于:月萌api www.moonapi.com,转载请注明出处