算法设计：求二叉树的垂直宽度|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是二叉树的高度。递归调用需要大量空间。