Dado un árbol binario, encuentre el ancho vertical del árbol binario. El ancho de un árbol binario es el número de caminos verticales.
Ejemplos:
C++
// CPP code to find vertical
// width of a binary tree
#include <bits/stdc++.h>
using namespace std;
// Tree class
class Node
{
public :
int data;
Node *left, *right;
// Constructor
Node(int data_new)
{
data = data_new;
left = right = NULL;
}
};
// Function to fill hd in set.
void fillSet(Node* root, unordered_set<int>& s,
int hd)
{
if (!root)
return;
fillSet(root->left, s, hd - 1);
s.insert(hd);
fillSet(root->right, s, hd + 1);
}
int verticalWidth(Node* root)
{
unordered_set<int> s;
// Third parameter is horizontal
// distance
fillSet(root, s, 0);
return s.size();
}
int main()
{
Node* root = NULL;
// Creating the above tree
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->right->left = new Node(6);
root->right->right = new Node(7);
root->right->left->right = new Node(8);
root->right->right->right = new Node(9);
cout << verticalWidth(root) << "\n";
return 0;
}
Java
/* Java code to find the vertical width of a binary tree */
import java.io.*;
import java.util.*;
/* A binary tree node has data, pointer to left child
and a pointer to right child */
class Node
{
int data;
Node left, right;
Node(int item)
{
data = item;
left = right = null;
}
}
class BinaryTree
{
Node root;
/* UTILITY FUNCTIONS */
// Function to fill hd in set.
void fillSet(Node root,Set<Integer> set,int hd)
{
if(root == null) return;
fillSet(root.left,set,hd - 1);
set.add(hd);
fillSet(root.right,set,hd + 1);
}
int verticalWidth(Node root)
{
Set<Integer> set = new HashSet<Integer>();
// Third parameter is horizontal distance
fillSet(root,set,0);
return set.size();
}
/* Driver program to test above functions */
public static void main(String args[])
{
BinaryTree tree = new BinaryTree();
/*
Constructed binary tree is:
1
/ \
2 3
/ \ \
4 5 8
/ \
6 7
*/
tree.root = new Node(1);
tree.root.left = new Node(2);
tree.root.right = new Node(3);
tree.root.left.left = new Node(4);
tree.root.left.right = new Node(5);
tree.root.right.right = new Node(8);
tree.root.right.right.left = new Node(6);
tree.root.right.right.right = new Node(7);
System.out.println(tree.verticalWidth(tree.root));
}
}
/* This code is contributed by Ashok Borra */
Python3
# Python code to find vertical # width of a binary tree class Node: def __init__(self, data): self.data = data self.left = self.right = None # Function to fill hd in set. def fillSet(root, s, hd): if (not root): return fillSet(root.left, s, hd - 1) s.add(hd) fillSet(root.right, s, hd + 1) def verticalWidth(root): s = set() # Third parameter is horizontal # distance fillSet(root, s, 0) return len(s) if __name__ == '__main__': # Creating the above tree root = Node(1) root.left = Node(2) root.right = Node(3) root.left.left = Node(4) root.left.right = Node(5) root.right.left = Node(6) root.right.right = Node(7) root.right.left.right = Node(8) root.right.right.right = Node(9) print(verticalWidth(root)) # This code is contributed by PranchalK
C#
// C# code to find the vertical width
// of a binary tree
using System;
using System.Collections.Generic;
/* A binary tree node has data,
pointer to left child and a
pointer to right child */
public class Node
{
public int data;
public Node left, right;
public Node(int item)
{
data = item;
left = right = null;
}
}
public class BinaryTree
{
Node root;
/* UTILITY FUNCTIONS */
// Function to fill hd in set.
void fillSet(Node root, HashSet<int> set, int hd)
{
if(root == null) return;
fillSet(root.left, set, hd - 1);
set.Add(hd);
fillSet(root.right, set, hd + 1);
}
int verticalWidth(Node root)
{
HashSet<int> set = new HashSet<int>();
// Third parameter is horizontal distance
fillSet(root,set, 0);
return set.Count;
}
// Driver Code
public static void Main(String []args)
{
BinaryTree tree = new BinaryTree();
/*
Constructed binary tree is:
1
/ \
2 3
/ \ \
4 5 8
/ \
6 7
*/
tree.root = new Node(1);
tree.root.left = new Node(2);
tree.root.right = new Node(3);
tree.root.left.left = new Node(4);
tree.root.left.right = new Node(5);
tree.root.right.right = new Node(8);
tree.root.right.right.left = new Node(6);
tree.root.right.right.right = new Node(7);
Console.WriteLine(tree.verticalWidth(tree.root));
}
}
// This code is contributed by PrinciRaj1992
Javascript
<script>
// Javascript code to find the vertical
// width of a binary tree
/* A binary tree node has data,
pointer to left child and a
pointer to right child */
class Node
{
constructor(item)
{
this.data = item;
this.left = null;
this.right = null;
}
}
var root;
/* UTILITY FUNCTIONS */
// Function to fill hd in set.
function fillSet(root,set, hd)
{
if (root == null)
return;
fillSet(root.left, set, hd - 1);
set.add(hd);
fillSet(root.right, set, hd + 1);
}
function verticalWidth(root)
{
var set = new Set();
// Third parameter is horizontal
// distance
fillSet(root,set, 0);
return set.size;
}
// Driver Code
/*
Constructed binary tree is:
1
/ \
2 3
/ \ \
4 5 8
/ \
6 7
*/
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.right.right = new Node(8);
root.right.right.left = new Node(6);
root.right.right.right = new Node(7);
document.write(verticalWidth(root));
// This code is contributed by rrrtnx
</script>
Publicación traducida automáticamente
Artículo escrito por Aashish Chauhan y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA