Encuentre la altura de un árbol binario especial cuyos Nodes hoja están conectados

Dado un árbol binario especial cuyos Nodes hoja están conectados para formar una lista circular doblemente enlazada, encuentre su altura.

Por ejemplo, 

         1 
       /   \ 
      2      3 
    /  \ 
   4    5
  /   
 6 

En el árbol binario anterior, 6, 5 y 3 son Nodes hoja y forman una lista circular doblemente enlazada. Aquí, el puntero izquierdo del Node hoja actuará como puntero anterior de la lista circular doblemente enlazada y su puntero derecho actuará como el siguiente puntero de la lista circular doblemente enlazada. 

La idea es seguir un enfoque similar al que usamos para encontrar la altura de un árbol binario normal. Calculamos recursivamente la altura de los subárboles izquierdo y derecho de un Node y asignamos la altura al Node como el máximo de las alturas de dos hijos más 1. Pero los hijos izquierdo y derecho de un Node hoja son nulos para los árboles binarios normales. Pero, aquí el Node de hoja es un Node de lista circular doblemente vinculado. Entonces, para que un Node sea un Node hoja, verificamos si la derecha de la izquierda del Node apunta al Node y si la izquierda de la derecha también apunta al Node en sí.

A continuación se muestra la implementación de la idea anterior:  

// C++ program to calculate height of a special tree
// whose leaf nodes forms a circular doubly linked list
#include <bits/stdc++.h>
using namespace std;
 
// A binary tree Node
struct Node {
    int data;
    Node *left, *right;
};
 
// function to check if given node is a leaf node or node
bool isLeaf(Node* node)
{
    // If given node's left's right is pointing to given
    // node and its right's left is pointing to the node
    // itself then it's a leaf
    return node->left && node->left->right == node
           && node->right && node->right->left == node;
}
 
/* Compute the height of a tree -- the number of
Nodes along the longest path from the root node
down to the farthest leaf node.*/
int maxDepth(Node* node)
{
    // if node is NULL, return 0
    if (node == NULL)
        return 0;
 
    // if node is a leaf node, return 1
    if (isLeaf(node))
        return 1;
 
    // compute the depth of each subtree and take maximum
    return 1
           + max(maxDepth(node->left),
                 maxDepth(node->right));
}
 
// Helper function that allocates a new tree node
Node* newNode(int data)
{
    Node* node = new Node;
    node->data = data;
    node->left = NULL;
    node->right = NULL;
 
    return node;
}
 
// Driver code
int main()
{
    Node* root = newNode(1);
 
    root->left = newNode(2);
    root->right = newNode(3);
    root->left->left = newNode(4);
    root->left->right = newNode(5);
    root->left->left->left = newNode(6);
 
    // Given tree contains 3 leaf nodes
    Node* L1 = root->left->left->left;
    Node* L2 = root->left->right;
    Node* L3 = root->right;
 
    // create circular doubly linked list out of
    // leaf nodes of the tree
 
    // set next pointer of linked list
    L1->right = L2, L2->right = L3, L3->right = L1;
 
    // set prev pointer of linked list
    L3->left = L2, L2->left = L1, L1->left = L3;
 
    // calculate height of the tree
    cout << "Height of tree is " << maxDepth(root);
 
    return 0;
}

// Java implementation to calculate height of a special tree
// whose leaf nodes forms a circular doubly linked list
import java.io.*;
import java.util.*;
 
// User defined node class
class Node {
    int data;
    Node left, right;
    // Constructor to create a new tree node
    Node(int key)
    {
        data = key;
        left = right = null;
    }
}
 
class GFG {
 
    // function to check if given node is a leaf node or
    // node
    static boolean isLeaf(Node node)
    {
        // If given node's left's right is pointing to given
        // node and its right's left is pointing to the node
        // itself then it's a leaf
        return (node.left != null && node.left.right == node
                && node.right != null
                && node.right.left == node);
    }
    /* Compute the height of a tree -- the number of
    Nodes along the longest path from the root node
    down to the farthest leaf node.*/
    static int maxDepth(Node node)
    {
        // if node is NULL, return 0
        if (node == null)
            return 0;
 
        // if node is a leaf node, return 1
        if (isLeaf(node))
            return 1;
 
        // compute the depth of each subtree and take
        // maximum
        return 1
            + Math.max(maxDepth(node.left),
                       maxDepth(node.right));
    }
 
    // Driver code
    public static void main(String args[])
    {
        Node root = new Node(1);
 
        root.left = new Node(2);
        root.right = new Node(3);
        root.left.left = new Node(4);
        root.left.right = new Node(5);
        root.left.left.left = new Node(6);
 
        // Given tree contains 3 leaf nodes
        Node L1 = root.left.left.left;
        Node L2 = root.left.right;
        Node L3 = root.right;
 
        // create circular doubly linked list out of
        // leaf nodes of the tree
 
        // set next pointer of linked list
        L1.right = L2;
        L2.right = L3;
        L3.right = L1;
 
        // set prev pointer of linked list
        L3.left = L2;
        L2.left = L1;
        L1.left = L3;
 
        // calculate height of the tree
        System.out.println("Height of tree is "
                           + maxDepth(root));
    }
}
// This code is contributed by rachana soma

""" program to Delete a Tree """
 
# Helper function that allocates a new
# node with the given data and None
# left and right pointers.
 
 
class newNode:
 
    # Construct to create a new node
    def __init__(self, key):
        self.data = key
        self.left = None
        self.right = None
 
# function to check if given node is a leaf node or node
 
 
def isLeaf(node):
 
    # If given node's left's right is pointing to given node
    # and its right's left is pointing to the node itself
    # then it's a leaf
    return node.left and node.left.right == node and \
        node.right and node.right.left == node
 
 
""" Compute the height of a tree -- the number of
Nodes along the longest path from the root node
down to the farthest leaf node."""
 
 
def maxDepth(node):
 
    # if node is None, return 0
    if (node == None):
        return 0
 
    # if node is a leaf node, return 1
    if (isLeaf(node)):
        return 1
 
    # compute the depth of each subtree and take maximum
    return 1 + max(maxDepth(node.left), maxDepth(node.right))
 
 
# Driver Code
if __name__ == '__main__':
    root = newNode(1)
 
    root.left = newNode(2)
    root.right = newNode(3)
    root.left.left = newNode(4)
    root.left.right = newNode(5)
    root.left.left.left = newNode(6)
 
    # Given tree contains 3 leaf nodes
    L1 = root.left.left.left
    L2 = root.left.right
    L3 = root.right
 
    # create circular doubly linked list out of
    # leaf nodes of the tree
 
    # set next pointer of linked list
    L1.right = L2
    L2.right = L3
    L3.right = L1
 
    # set prev pointer of linked list
    L3.left = L2
    L2.left = L1
    L1.left = L3
 
    # calculate height of the tree
    print("Height of tree is ", maxDepth(root))
 
# This code is contributed by
# Shubham Singh(SHUBHAMSINGH10)

// C# implementation to calculate height of a special tree
// whose leaf nodes forms a circular doubly linked list
using System;
 
// User defined node class
public class Node {
    public int data;
    public Node left, right;
    // Constructor to create a new tree node
    public Node(int key)
    {
        data = key;
        left = right = null;
    }
}
 
public class GFG {
 
    // function to check if given node is a leaf node or
    // node
    static bool isLeaf(Node node)
    {
        // If given node's left's right is pointing to given
        // node and its right's left is pointing to the node
        // itself then it's a leaf
        return (node.left != null && node.left.right == node
                && node.right != null
                && node.right.left == node);
    }
    /* Compute the height of a tree -- the number of
    Nodes along the longest path from the root node
    down to the farthest leaf node.*/
    static int maxDepth(Node node)
    {
        // if node is NULL, return 0
        if (node == null)
            return 0;
 
        // if node is a leaf node, return 1
        if (isLeaf(node))
            return 1;
 
        // compute the depth of each subtree and take
        // maximum
        return 1
            + Math.Max(maxDepth(node.left),
                       maxDepth(node.right));
    }
 
    // Driver code
    public static void Main(String[] args)
    {
        Node root = new Node(1);
 
        root.left = new Node(2);
        root.right = new Node(3);
        root.left.left = new Node(4);
        root.left.right = new Node(5);
        root.left.left.left = new Node(6);
 
        // Given tree contains 3 leaf nodes
        Node L1 = root.left.left.left;
        Node L2 = root.left.right;
        Node L3 = root.right;
 
        // create circular doubly linked list out of
        // leaf nodes of the tree
 
        // set next pointer of linked list
        L1.right = L2;
        L2.right = L3;
        L3.right = L1;
 
        // set prev pointer of linked list
        L3.left = L2;
        L2.left = L1;
        L1.left = L3;
 
        // calculate height of the tree
        Console.WriteLine("Height of tree is "
                          + maxDepth(root));
    }
}
 
// This code is contributed by 29AjayKumar

<script>
// Javascript implementation to calculate height of a special tree
// whose leaf nodes forms a circular doubly linked list
class Node
{
    constructor(key)
    {
        this.data = key;
        this.left = this.right = null;
    }
}
 
// function to check if given node is a leaf node or
    // node
function isLeaf(node)
{
 
    // If given node's left's right is pointing to given
        // node and its right's left is pointing to the node
        // itself then it's a leaf
        return (node.left != null && node.left.right == node
                && node.right != null
                && node.right.left == node);
}
 
/* Compute the height of a tree -- the number of
    Nodes along the longest path from the root node
    down to the farthest leaf node.*/
function maxDepth(node)
{
 
     // if node is NULL, return 0
        if (node == null)
            return 0;
   
        // if node is a leaf node, return 1
        if (isLeaf(node))
            return 1;
   
        // compute the depth of each subtree and take
        // maximum
        return 1
            + Math.max(maxDepth(node.left),
                       maxDepth(node.right));
}
 
// Driver code
let root = new Node(1);
   
root.left = new Node(2);
root.right = new Node(3);
root.left.left = new Node(4);
root.left.right = new Node(5);
root.left.left.left = new Node(6);
 
// Given tree contains 3 leaf nodes
let L1 = root.left.left.left;
let L2 = root.left.right;
let L3 = root.right;
 
// create circular doubly linked list out of
// leaf nodes of the tree
 
// set next pointer of linked list
L1.right = L2;
L2.right = L3;
L3.right = L1;
 
// set prev pointer of linked list
L3.left = L2;
L2.left = L1;
L1.left = L3;
 
// calculate height of the tree
document.write("Height of tree is "
                   + maxDepth(root));
 
// This code is contributed by rag2127
</script>

Height of tree is 4

Este artículo es una contribución de Aditya Goel . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.