Estou tentando executar este método, mas sempre dar false na comparação. Assim não armazena os dados e não gera a saida desejada. Alguém sabe dizer como posso resolver este problema?
static Vector<Integer> 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);
}
Qual comparação? Tem 2 ifs no seu código, com 5 comparações no total.
Se nada do método deve executar, você pode dar return direto:
static void printNodesOneChild(Node root){
return;
// resto do código, tornado irrelevante
Se for o primeiro if, algo como:
static void printNodesOneChild(Node root)
{
root = null; // muda root pra null, daí já não passa do primeiro if
// Base case
if (root == null)
return;
Isso serve para o segundo if também, se você mudar o root = null para após o primeiro return.
Você também pode mudar o root.left e root.right pra null após o primeiro if e return, com basicamente o mesmo efeito.
Por fim, pode comentar a linha list.add, e as chamadas posteriores à printNodesOneChild. Assim, não precisa mudar os valores de root e de root.left/root.right.
Pedi para mostrar o conteudo de root.left e ele mostrou o seguinte resultado.
HuxleyCode$Node@58372a00
HuxleyCode$Node@4dd8dc3
HuxleyCode$Node@6d03e736
HuxleyCode$Node@568db2f2
null
null
null
HuxleyCode$Node@378bf509
HuxleyCode$Node@5fd0d5ae
null
null
HuxleyCode$Node@2d98a335
null
null
Era para ignorar o null e armazenar os valores diferentes de null, mas não está fazendo isso.
Ignora todos os casos…
Desculpe, não ficou claro no seu primeiro post que era isso que você queria.
O código original desse método (sem as alterações que sugeri) serve pra percorrer os nós e armazenar aqueles que só tem 1 nó filho (left ou right). É isso que você esperava? Tem outros métodos nessa classe além desse?
Mostre o seu código, especialmente onde está sendo feito o print (não é nesse método, não tem nenhum print nele).
Esse é o código completo, o print está sendo realizado na classe principal…
/*
* A binary tree node has data, pointer to left child and a pointer to right
* child
*/
public static class Node {
int data;
Node left, right;
Node(int data) {
this.data = data;
}
}
// static variable to point to the
// starting index of the string.
static int start = 1;
// Construct Tree Function which accepts
// a string and return root of the tree;
static Node constructTree(String s) {
// Check for null or empty string
// and return null;
if (s.length() == 0 || s == null) {
return null;
}
if (start >= s.length())
return null;
// Boolean variable to check
// for negative numbers
boolean neg = false;
// Condition to check for negative number
if (s.charAt(start) == '-') {
neg = true;
start++;
}
// This loop basically construct the
// number from the continuous digits
int num = 0;
while (start < s.length() && Character.isDigit(s.charAt(start))) {
int digit = Character.getNumericValue(s.charAt(start));
num = num * 10 + digit;
start++;
}
// If string contains - minus sign
// then append - to the number;
if (neg)
num = -num;
// Create the node object i.e. root of
// the tree with data = num;
Node node = new Node(num);
if (start >= s.length()) {
return node;
}
// Check for open bracket and add the
// data to the left subtree recursively
if (start < s.length() && s.charAt(start) == '(') {
start++;
node.left = constructTree(s);
}
if (start < s.length() && s.charAt(start) == ')') {
start++;
return node;
}
// Check for open bracket and add the data
// to the right subtree recursively
if (start < s.length() && s.charAt(start) == '(') {
start++;
node.right = constructTree(s);
}
if (start < s.length() && s.charAt(start) == ')') {
start++;
return node;
}
return node;
}
static Vector<Integer> list = new Vector<>();
// Function to find the nodes
// having single child
public static void printNodesOneChild(Node root)
{
// Base case
if (root == null)
return;
// Condition to check if the node
// is having only one child
System.out.println(root.right.data );
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) {
Scanner input = new Scanner(System.in);
// Input
String s = "(33(9(0(1()())())(2(3()())(4()())))(11(5()(6()()))(8(7()())())))";
//String s = "(7(11(9()())(2()()))(13(0()())(1()())))";
// Call the function cunstruct tree
// to create the tree pass the string;
Node root = constructTree(s);
// Function to print preorder of the tree
printTree(root);
printNodesOneChild(root);
// Condition to check if there is
// no such node having single child
System.out.println(list.size());
if (list.size() == 0)
System.out.println(-1);
else
{
for(int value : list)
{
System.out.println(value);
}
}
}
System.out.println();
}
Sua alteração no printNodesOneChild() está imprimindo o nó direito, que pode estar nulo, e não é o nó que você deve imprimir. Você deve imprimir o nó “root”, não o “root.right”.
public static void printNodesOneChild(Node root)
{
// Base case
if (root == null)
return;
// Condition to check if the node
// is having only one child
System.out.println(root.data); // alterado de root.right.data
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);
}