Dado un árbol binario, encuentre el ancho vertical del árbol binario. El ancho de un árbol binario es el número de caminos verticales.
C++
// CPP program to print vertical width
// of a tree
#include <bits/stdc++.h>
using namespace std;
// A Binary Tree Node
struct Node
{
int data;
struct Node *left, *right;
};
// get vertical width
void lengthUtil(Node* root, int &maximum,
int &minimum, int curr=0)
{
if (root == NULL)
return;
// traverse left
lengthUtil(root->left, maximum,
minimum, curr - 1);
// if curr is decrease then get
// value in minimum
if (minimum > curr)
minimum = curr;
// if curr is increase then get
// value in maximum
if (maximum < curr)
maximum = curr;
// traverse right
lengthUtil(root->right, maximum,
minimum, curr + 1);
}
int getLength(Node* root)
{
int maximum = 0, minimum = 0;
lengthUtil(root, maximum, minimum, 0);
// 1 is added to include root in the width
return (abs(minimum) + maximum) + 1;
}
// Utility function to create a new tree node
Node* newNode(int data)
{
Node* curr = new Node;
curr->data = data;
curr->left = curr->right = NULL;
return curr;
}
// Driver program to test above functions
int main()
{
Node* root = newNode(7);
root->left = newNode(6);
root->right = newNode(5);
root->left->left = newNode(4);
root->left->right = newNode(3);
root->right->left = newNode(2);
root->right->right = newNode(1);
cout << getLength(root) << "\n";
return 0;
}
Java
// Java program to print vertical width
// of a tree
import java.util.*;
class GFG
{
// A Binary Tree Node
static class Node
{
int data;
Node left, right;
};
static int maximum = 0, minimum = 0;
// get vertical width
static void lengthUtil(Node root, int curr)
{
if (root == null)
return;
// traverse left
lengthUtil(root.left, curr - 1);
// if curr is decrease then get
// value in minimum
if (minimum > curr)
minimum = curr;
// if curr is increase then get
// value in maximum
if (maximum < curr)
maximum = curr;
// traverse right
lengthUtil(root.right, curr + 1);
}
static int getLength(Node root)
{
maximum = 0; minimum = 0;
lengthUtil(root, 0);
// 1 is added to include root in the width
return (Math.abs(minimum) + maximum) + 1;
}
// Utility function to create a new tree node
static Node newNode(int data)
{
Node curr = new Node();
curr.data = data;
curr.left = curr.right = null;
return curr;
}
// Driver Code
public static void main(String[] args)
{
Node root = newNode(7);
root.left = newNode(6);
root.right = newNode(5);
root.left.left = newNode(4);
root.left.right = newNode(3);
root.right.left = newNode(2);
root.right.right = newNode(1);
System.out.println(getLength(root));
}
}
// This code is contributed by Rajput-Ji
Python3
# Python3 program to print vertical width # of a tree # class to create a new tree node class newNode: def __init__(self, data): self.data = data self.left = self.right = None # get vertical width def lengthUtil(root, maximum, minimum, curr = 0): if (root == None): return # traverse left lengthUtil(root.left, maximum, minimum, curr - 1) # if curr is decrease then get # value in minimum if (minimum[0] > curr): minimum[0] = curr # if curr is increase then get # value in maximum if (maximum[0] < curr): maximum[0] = curr # traverse right lengthUtil(root.right, maximum, minimum, curr + 1) def getLength(root): maximum = [0] minimum = [0] lengthUtil(root, maximum, minimum, 0) # 1 is added to include root in the width return (abs(minimum[0]) + maximum[0]) + 1 # Driver Code if __name__ == '__main__': root = newNode(7) root.left = newNode(6) root.right = newNode(5) root.left.left = newNode(4) root.left.right = newNode(3) root.right.left = newNode(2) root.right.right = newNode(1) print(getLength(root)) # This code is contributed by PranchalK
C#
// C# program to print vertical width
// of a tree
using System;
class GFG
{
// A Binary Tree Node
public class Node
{
public int data;
public Node left, right;
};
static int maximum = 0, minimum = 0;
// get vertical width
static void lengthUtil(Node root,
int curr)
{
if (root == null)
return;
// traverse left
lengthUtil(root.left, curr - 1);
// if curr is decrease then get
// value in minimum
if (minimum > curr)
minimum = curr;
// if curr is increase then get
// value in maximum
if (maximum < curr)
maximum = curr;
// traverse right
lengthUtil(root.right, curr + 1);
}
static int getLength(Node root)
{
maximum = 0; minimum = 0;
lengthUtil(root, 0);
// 1 is added to include root in the width
return (Math.Abs(minimum) + maximum) + 1;
}
// Utility function to create a new tree node
static Node newNode(int data)
{
Node curr = new Node();
curr.data = data;
curr.left = curr.right = null;
return curr;
}
// Driver Code
public static void Main(String[] args)
{
Node root = newNode(7);
root.left = newNode(6);
root.right = newNode(5);
root.left.left = newNode(4);
root.left.right = newNode(3);
root.right.left = newNode(2);
root.right.right = newNode(1);
Console.WriteLine(getLength(root));
}
}
// This code is contributed by PrinciRaj1992
Javascript
<script>
// JavaScript program to prvertical width
// of a tree
// class to create a new tree node
class newNode{
constructor(data){
this.data = data
this.left = this.right = null
}
}
// get vertical width
function lengthUtil(root, maximum, minimum, curr = 0){
if (root == null)
return
// traverse left
lengthUtil(root.left, maximum,
minimum, curr - 1)
// if curr is decrease then get
// value in minimum
if (minimum[0] > curr)
minimum[0] = curr
// if curr is increase then get
// value in maximum
if (maximum[0] <curr)
maximum[0] = curr
// traverse right
lengthUtil(root.right, maximum,
minimum, curr + 1)
}
function getLength(root)
{
let maximum = [0]
let minimum = [0]
lengthUtil(root, maximum, minimum, 0)
// 1 is added to include root in the width
return (Math.abs(minimum[0]) + maximum[0]) + 1
}
// Driver Code
root = new newNode(7)
root.left = new newNode(6)
root.right = new newNode(5)
root.left.left = new newNode(4)
root.left.right = new newNode(3)
root.right.left = new newNode(2)
root.right.right = new newNode(1)
document.write(getLength(root),"</br>")
// This code is contributed by shinjanpatra.
</script>
Java
// Java program to print vertical width
// of a tree
import java.util.*;
class GFG
{
// A Binary Tree Node
static class Node
{
int data;
Node left, right;
};
static class Pair{
Node node;
int level; //Horizontal Level
Pair(Node node,int level){
this.node = node;
this.level = level;
}
}
static int maxLevel = 0, minLevel = 0;
// get vertical width
static void lengthUtil(Node root)
{
Queue<Pair> q = new ArrayDeque<>();
//Adding the root node initially with level as 0;
q.add(new Pair(root,0));
while(q.size() > 0){
//removing the node at the peek of queue;
Pair rem = q.remove();
//If the left child of removed node exists
if(rem.node.left != null){
//level of the left child will be 1 less than its parent
q.add(new Pair(rem.node.left,rem.level-1));
//updating the minLevel
minLevel=Math.min(minLevel,rem.level-1);
}
//If the right child of removed node exists
if(rem.node.right != null){
//level of the right child will be 1 more than its parent
q.add(new Pair(rem.node.right,rem.level+1));
//updating the minLevel
maxLevel=Math.max(minLevel,rem.level+1);
}
}
}
static int getLength(Node root)
{
maxLevel = 0; minLevel = 0;
lengthUtil(root);
// 1 is added to include root in the width
return (Math.abs(minLevel) + maxLevel) + 1;
}
// Utility function to create a new tree node
static Node newNode(int data)
{
Node curr = new Node();
curr.data = data;
curr.left = curr.right = null;
return curr;
}
// Driver Code
public static void main(String[] args)
{
Node root = newNode(7);
root.left = newNode(6);
root.right = newNode(5);
root.left.left = newNode(4);
root.left.right = newNode(3);
root.right.left = newNode(2);
root.right.right = newNode(1);
System.out.println(getLength(root));
}
}
// This code is contributed by Archit Sharma
C++
// C++ program to find Vetical Height of a tree
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
struct Node
{
int data;
struct Node* left;
struct Node* right;
Node(int x){
data = x;
left = right = NULL;
}
};
int verticalWidth(Node* root)
{
// Code here
if(root == NULL)
return 0;
int maxLevel = 0,minLevel = 0;
queue<pair<Node*,int>> q;
q.push({root,0}); // we take root as 0
//Level order traversal code
while(q.empty() != true)
{
Node *cur = q.front().first;
int count = q.front().second;
q.pop();
if(cur->left)
{
minLevel = min(minLevel, count - 1); // as we go left, level is decreased
q.push({cur->left, count - 1});
}
if(cur->right)
{
maxLevel = max(maxLevel, count + 1); // as we go right, level is increased
q.push({cur->right, count + 1});
}
}
return maxLevel + abs(minLevel) + 1; // +1 for the root node, we gave it a value of zero
}
int main() {
// making the tree
Node *root = new Node(7);
root->left = new Node(6);
root->right = new Node(5);
root->left->left = new Node(4);
root->left->right = new Node(3);
root->right->left = new Node(2);
root->right->right = new Node(1);
cout << "Vertical width is : " << verticalWidth(root) << endl
;
return 0;
}
// code contributed by Anshit Bansal
Publicación traducida automáticamente
Artículo escrito por DevanshuAgarwal y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA