原文:

给定一个二叉树，任务是打印有孙子的节点。

示例:

输入:

输出: 20 8 说明: 20 和 8 是 4、12 和 10、14 的祖辈。

输入:

输出: 1 说明: 1 是 4、5 的祖父母。

方法:思路采用。以下是步骤:

  1. 在每个节点遍历给定的树。
  2. 检查每个节点是否有子节点。
  3. 对于任何树节点(比如 temp )，如果下面的节点之一存在，那么当前节点就是祖父节点:
    • temp->左侧->左侧。
    • temp->左->右。
    • temp->右->左。
    • temp->right->right。
  4. 如果任何节点 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，转载请注明出处

本文链接：http://www.moonapi.com/news/38737.html