算法设计（求二叉树的垂直宽度|S1）

本文概述

C ++
Java
Python3
C#

给定一棵二叉树, 找到二叉树的垂直宽度。二叉树的宽度是垂直路径的数量。

文章图片
【算法设计（求二叉树的垂直宽度|S1）】在此图像中, 树包含6条垂直线, 这是树的所需宽度。
例子：

Input : 7 /\ 65 / \/ \ 43 21 Output : 5Input : 1 /\ 23 / \/ \ 4567 \\ 89 Output : 6

方法：
如果我们向左走, 则进行有序遍历, 然后获取一个临时变量, 则温度值减小；如果向右走, 则温度值增大。声明一个条件, 如果最小值大于temp, 则最小值= temp, 如果最大值小于temp, 则最大值= temp。最后, 打印最小+最大, 即树的垂直宽度。
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 = http://www.srcmini.com/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 = http://www.srcmini.com/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 prvertical width # of a tree # class to create a new tree node class newNode: def __init__( self , data): self .data = http://www.srcmini.com/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# 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 = http://www.srcmini.com/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

输出如下：