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

本文概述

• C ++
• Java
• Python3
• C#

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

在此图像中, 树包含6条垂直线, 这是树的所需宽度。

例子 ：

Input : 7 / \ 6 5 / \ / \ 4 3 2 1 Output : 5 Input : 1 / \ 2 3 / \ / \ 4 5 6 7 \ \ 8 9 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 = 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 prvertical 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

输出如下：

5

时间复杂度：O(n)

辅助空间：O(h)其中h是二叉树的高度。递归调用需要大量空间。