Compruebe si el recorrido en orden de un árbol binario es palíndromo o no

Dado un árbol binario y la tarea de verificar si su Inorder Sequence es un palíndromo o no. 
Ejemplos: 
 

Aporte: 
 

Salida: Verdadero 
Explicación: 
La secuencia Inorder del árbol es «bbaaabb», que es una string palindrómica.
Aporte: 
 

Salida: Falso 
Explicación: 
La secuencia Inorder del árbol es «bbdaabb», que no es una string palindrómica. 
 

Enfoque: 
Para resolver el problema, consulte los siguientes pasos: 
 

• Convierta el árbol binario dado en una lista doblemente enlazada .
• Esto reduce el problema a Comprobar si una lista de caracteres doblemente enlazada es palíndromo o no .

A continuación se muestra la implementación del enfoque anterior: 
 

// C++ Program to check if
// the Inorder sequence of a
// Binary Tree is a palindrome
 
#include <bits/stdc++.h>
using namespace std;
 
// Define node of tree
struct node {
    char val;
    node* left;
    node* right;
};
 
// Function to create the node
node* newnode(char i)
{
    node* temp = NULL;
    temp = new node();
    temp->val = i;
    temp->left = NULL;
    temp->right = NULL;
    return temp;
}
 
// Function to convert the tree
// to the double linked list
node* conv_tree(node* root,
                node* shoot)
{
    if (root->left != NULL)
        shoot = conv_tree(root->left,
                          shoot);
 
    root->left = shoot;
 
    if (shoot != NULL)
        shoot->right = root;
 
    shoot = root;
 
    if (root->right != NULL)
        shoot = conv_tree(root->right,
                          shoot);
 
    return shoot;
}
 
// Function for checking linked
// list is palindrome or not
int checkPalin(node* root)
{
    node* voot = root;
 
    // Count the nodes
    // form the back
    int j = 0;
 
    // Set the pointer at the
    // very first node of the
    // linklist and count the
    // length of the linklist
    while (voot->left != NULL) {
        j = j + 1;
        voot = voot->left;
    }
    int i = 0;
 
    while (i < j) {
        // Check if the value matches
        if (voot->val != root->val)
            return 0;
 
        else {
            i = i + 1;
            j = j - 1;
            voot = voot->right;
            root = root->left;
        }
    }
 
    return 1;
}
 
// Driver Program
int main()
{
    node* root = newnode('b');
    root->left = newnode('b');
    root->right = newnode('a');
    root->left->right = newnode('b');
    root->left->left = newnode('a');
 
    node* shoot = conv_tree(root, NULL);
 
    if (checkPalin(shoot))
        cout << "True" << endl;
    else
        cout << "False" << endl;
}

// Java Program to check if
// the Inorder sequence of a
// Binary Tree is a palindrome
import java.util.*;
class GFG{
 
// Define node of tree
static class node
{
    char val;
    node left;
    node right;
};
 
// Function to create the node
static node newnode(char i)
{
    node temp = null;
    temp = new node();
    temp.val = i;
    temp.left = null;
    temp.right = null;
    return temp;
}
 
// Function to convert the tree
// to the double linked list
static node conv_tree(node root,
                      node shoot)
{
    if (root.left != null)
        shoot = conv_tree(root.left,
                          shoot);
 
    root.left = shoot;
 
    if (shoot != null)
        shoot.right = root;
 
    shoot = root;
 
    if (root.right != null)
        shoot = conv_tree(root.right,
                          shoot);
 
    return shoot;
}
 
// Function for checking linked
// list is palindrome or not
static int checkPalin(node root)
{
    node voot = root;
 
    // Count the nodes
    // form the back
    int j = 0;
 
    // Set the pointer at the
    // very first node of the
    // linklist and count the
    // length of the linklist
    while (voot.left != null)
    {
        j = j + 1;
        voot = voot.left;
    }
    int i = 0;
 
    while (i < j)
    {
        // Check if the value matches
        if (voot.val != root.val)
            return 0;
 
        else
        {
            i = i + 1;
            j = j - 1;
            voot = voot.right;
            root = root.left;
        }
    }
    return 1;
}
 
// Driver Code
public static void main(String[] args)
{
    node root = newnode('b');
    root.left = newnode('b');
    root.right = newnode('a');
    root.left.right = newnode('b');
    root.left.left = newnode('a');
 
    node shoot = conv_tree(root, null);
 
    if (checkPalin(shoot) == 1)
        System.out.print("True" + "\n");
    else
        System.out.print("False" + "\n");
}
}
 
// This code is contributed by 29AjayKumar

# Python3 program to check if
# the Inorder sequence of a
# Binary Tree is a palindrome
 
# Define node of tree
class Node:
    def __init__(self,val):
         
        self.val = val
        self.left = None
        self.right = None
 
# Function to create the node
def newnode(i):
 
    #temp = None;
    temp = Node(i);
    temp.val = i;
    temp.left = None;
    temp.right = None;
    return temp;
 
# Function to convert the tree
# to the double linked list
def conv_tree(root, shoot):
 
    if (root.left != None):
        shoot = conv_tree(root.left, shoot);
 
    root.left = shoot;
 
    if (shoot != None):
        shoot.right = root;
 
    shoot = root;
 
    if (root.right != None):
        shoot = conv_tree(root.right, shoot);
 
    return shoot;
 
# Function for checking linked
# list is palindrome or not
def checkPalin(root):
 
    voot = root;
 
    # Count the nodes
    # form the back
    j = 0;
 
    # Set the pointer at the
    # very first node of the
    # linklist and count the
    # length of the linklist
    while (voot.left != None):
        j = j + 1;
        voot = voot.left;
     
    i = 0;
 
    while (i < j):
         
        # Check if the value matches
        if (voot.val != root.val):
            return 0;
        else:
            i = i + 1;
            j = j - 1;
            voot = voot.right;
            root = root.left;
             
    return 1;
 
# Driver code
if __name__=='__main__':
 
    root = newnode('b');
    root.left = newnode('b');
    root.right = newnode('a');
    root.left.right = newnode('b');
    root.left.left = newnode('a');
 
    shoot = conv_tree(root, None);
 
    if (checkPalin(shoot)):
        print("True");
    else:
        print("False");
 
# This code is contributed by AbhiThakur

// C# program to check if the inorder 
// sequence of a Binary Tree is a
// palindrome
using System;
 
class GFG{
 
// Define node of tree
class node
{
    public char val;
    public node left;
    public node right;
};
 
// Function to create the node
static node newnode(char i)
{
    node temp = null;
    temp = new node();
    temp.val = i;
    temp.left = null;
    temp.right = null;
 
    return temp;
}
 
// Function to convert the tree
// to the double linked list
static node conv_tree(node root,
                      node shoot)
{
    if (root.left != null)
        shoot = conv_tree(root.left,
                          shoot);
 
    root.left = shoot;
 
    if (shoot != null)
        shoot.right = root;
 
    shoot = root;
 
    if (root.right != null)
        shoot = conv_tree(root.right,
                          shoot);
 
    return shoot;
}
 
// Function for checking linked
// list is palindrome or not
static int checkPalin(node root)
{
    node voot = root;
 
    // Count the nodes
    // form the back
    int j = 0;
 
    // Set the pointer at the
    // very first node of the
    // linklist and count the
    // length of the linklist
    while (voot.left != null)
    {
        j = j + 1;
        voot = voot.left;
    }
    int i = 0;
 
    while (i < j)
    {
         
        // Check if the value matches
        if (voot.val != root.val)
            return 0;
        else
        {
            i = i + 1;
            j = j - 1;
            voot = voot.right;
            root = root.left;
        }
    }
    return 1;
}
 
// Driver Code
public static void Main(String[] args)
{
    node root = newnode('b');
    root.left = newnode('b');
    root.right = newnode('a');
    root.left.right = newnode('b');
    root.left.left = newnode('a');
 
    node shoot = conv_tree(root, null);
 
    if (checkPalin(shoot) == 1)
        Console.Write("True" + "\n");
    else
        Console.Write("False" + "\n");
}
}
 
// This code is contributed by 29AjayKumar

<script>
      // JavaScript program to check if the inorder
      // sequence of a Binary Tree is a
      // palindrome
      // Define node of tree
      class node {
        constructor() {
          this.val = 0;
          this.left = null;
          this.right = null;
        }
      }
 
      // Function to create the node
      function newnode(i) {
        var temp = null;
        temp = new node();
        temp.val = i;
        temp.left = null;
        temp.right = null;
 
        return temp;
      }
 
      // Function to convert the tree
      // to the double linked list
      function conv_tree(root, shoot) {
        if (root.left != null) shoot = conv_tree(root.left, shoot);
 
        root.left = shoot;
 
        if (shoot != null) shoot.right = root;
 
        shoot = root;
 
        if (root.right != null) shoot = conv_tree(root.right, shoot);
 
        return shoot;
      }
 
      // Function for checking linked
      // list is palindrome or not
      function checkPalin(root) {
        var voot = root;
 
        // Count the nodes
        // form the back
        var j = 0;
 
        // Set the pointer at the
        // very first node of the
        // linklist and count the
        // length of the linklist
        while (voot.left != null) {
          j = j + 1;
          voot = voot.left;
        }
        var i = 0;
 
        while (i < j) {
          // Check if the value matches
          if (voot.val != root.val) return 0;
          else {
            i = i + 1;
            j = j - 1;
            voot = voot.right;
            root = root.left;
          }
        }
        return 1;
      }
 
      // Driver Code
      var root = newnode("b");
      root.left = newnode("b");
      root.right = newnode("a");
      root.left.right = newnode("b");
      root.left.left = newnode("a");
 
      var shoot = conv_tree(root, null);
 
      if (checkPalin(shoot) == 1) document.write("True" + "<br>");
      else document.write("False" + "<br>");
       
      // This code is contributed by rdtank.
    </script>

True

Complejidad temporal: O(N) 
Espacio auxiliar: O(1)