二叉树的直径

2025年03月17日 | 阅读 9 分钟

二叉树的直径可以定义为连接二叉树中任意两个节点的最长路径的边数。二叉树的直径也称为二叉树的宽度。代表二叉树直径的路径可以经过二叉树的根节点，也可以不经过。路径包含两个叶节点，其中一个叶节点是计算直径的起点。

连接两个节点的最长路径，代表二叉树的直径，有两种可能：

经过根节点： 该路径将穿过二叉树的根节点，并且也计入根节点。
不经过根节点： 在这种情况下，所选路径将不穿过二叉树的根节点，并且在路径中不计入根节点。

在上图 1 中，最长路径连接叶节点 4 和叶节点 6，并且会经过根节点 1。图 1 中二叉树的直径为 6，从叶节点 4 到叶节点 6，即节点 4 - 节点 2 - 节点 1 - 节点 3 - 节点 5 - 节点 6，也包括根节点。

而在图 2 所示的二叉树中，连接两个节点的最长路径，用于计算二叉树的直径，是从叶节点 5 到叶节点 6 开始，但不包括根节点 1。该二叉树的直径为 5，沿路径节点 5 - 节点 3 - 节点 2 - 节点 4 - 节点 6，不包括根节点 1。

查找二叉树直径的方法

查找二叉树的直径是数据结构中一个非常常见的问题，有很多方法可以找到该问题的解决方案。现在我们对如何查找二叉树的直径有了一个概念，接下来让我们看看解决这个问题的不同方法或途径。

解决此问题有两种不同的方法：递归方法和迭代方法。两种方法都有不同的途径以及不同的时间和空间复杂度。

1. 递归方法

在这种方法中，使用递归函数查找两个子树的高度，然后借助这两个子树的高度，计算整个二叉树的直径。由于递归函数的重复调用，递归方法的时间和空间复杂度较高。

现在，我们用递归的方法来编写一个 Java 代码，用于查找二叉树的直径。

代码

// A Java Program to create a  Binary tree and then find the diameter of the Binary tree

// A class named Node is written that will act as the single node of the Binary tree

class Node
{
    // the Node class has Three class variables, one of Integer type and the rest two of Node class type having names data left and right, respectively 
    
    // the data variable is of Integer type and will be used to store the value that particular node is storing in the Binary tree
    int data;

    // the left and right variables are of a Node type and will be used to store the left sub child and right sub child of the Binary tree, respectively
    Node left = null, right = null;
 
// A parameterised constructor is also written that will be used to assign the value to the data variable for storing that value in the node of the Binary tree 
    Node(int data) {
        this.data = data;
    }
}//end of Node Class
 

// A class named BinaryTree is written to find the diameter of the Binary tree and print the result
class BinaryTree
{
    // Function to find the diameter of the binary tree. Note that the
    // function returns the height of the subtree rooted at a given node,
    // and the diameter is updated within the function as it is passed by
    // reference using the `AtomicInteger` class.
    // The getDiameter Function is the recursive function that will be called repeatedly to find the heights of both the left subtree and right subtree and
    // and then those heights will be used to calculate the diameter of the Binary tree
    
public static int getDiameter(Node root, AtomicInteger diameter)
    {
        // base case: tree is empty
        if (root == null) {
            return 0;
        }
 
        // get heights of left and right subtrees
        int left_height = getDiameter(root.left, diameter);
        int right_height = getDiameter(root.right, diameter);
 
        // calculate diameter "through" the current node
        int max_diameter = left_height + right_height + 1;
 
        // update maximum diameter (note that diameter "excluding" the current
        // node in the subtree rooted at the current node is already updated
        // since we are doing postorder traversal)
        diameter.set(Math.max(diameter.get(), max_diameter));
 
        // it is important to return the height of the subtree rooted at the
        // current node
        return Math.max(left_height, right_height) + 1;
    }
 

    there is one more definition of the getDiameter function with only one parameter that will be called from the main function that
    will return the actual diameter of the Binary tree    
    public static int getDiameter(Node root)
    {
        AtomicInteger diameter = new AtomicInteger(0);
        getDiameter(root, diameter);
 
        return diameter.get();
    }
 

    //main function is written to create a Binary tree and call the getDiameter() function to get the diameter of the Binary tree
    public static void main(String[] args)
    {
       // An Object of the Node class named root is created that will represent the root node of the Binary tree whose diameter is going to be calculated 
        Node root = new Node(500);
        
        //After the creation of the root node the childs to the root nodes are attached  
        root.left = new Node(895);
        root.right = new Node(123);
        root.left.right = new Node(412);
        root.right.left = new Node(345);
        root.right.right = new Node(236);
        root.right.left.left = new Node(247);
        root.right.left.right = new Node(448);
        
        // Once all the nodes are added in the Binary tree, the getDiameter() function is called to get the diameter of the Binary tree and the root node of the Binary tree is passed as a parameter to the getDiameter() function
        int diameter = getDiameter(root);
        System.out.print("The diameter of the binary tree is " + diameter);
    }
}

输出：上述代码的输出是

The diameter of the binary tree is 6

在上面的代码中，我们使用了名为 getDiameter() 的递归函数。该函数将被反复调用，以查找二叉树的左子树和右子树的高度，然后利用这些高度计算二叉树的直径。由于递归函数的重复调用，与迭代方法相比，时间复杂度和空间复杂度非常高。

查找二叉树直径的时间复杂度为：O(n^2)

查找二叉树直径的空间复杂度为：O(log n)

2. 迭代方法

不使用递归函数，而是以深度优先搜索的方式遍历二叉树，以查找二叉树的直径。由于我们以深度优先的方式遍历二叉树，这将帮助我们找到距离最深的或最远的叶节点，然后从该叶节点到另一个节点的路径将被计算以获得树的直径。此方法的时间和空间复杂度都较低。

在这个方法中，迭代方法的空间复杂度低于查找树直径的递归方法，因为没有重复的递归调用会增加这些复杂度。

现在，我们用迭代的方法来编写一个查找二叉树直径的代码。

代码

// A Java program to create a binary tree and find the diameter of that binary tree using DFS(iterative way). 


// The ArrayList class is imported from the java.util package
import java.util.ArrayList; 
// The Arrays class is imported from the java.util package
import java.util.Arrays;
// The List class is imported from the java.util package 
import java.util.List; 

// A class named BinaryTree is created to create a binary tree and find the diameter of that binary tree
public class BinaryTree { 
// Used to track farthest or the deepest leaf node of the binary tree. 
    static int x; 
    static int maxCount; 
    // A static Object of the List class is created to store the nodes of the binary tree whose diameter is to be calculated
    static List<Integer> nodes[]; 
      
    // A static Function named findDepth is created to find the deepest element of the binary tree, which is passed as a parameter to this Function
    
    // The findDepth() Function has four parameters two of Integer type named node and count and one is a boolean array named visited to mark the visited nodes and a List of Integer types named nodes representing the nodes of the binary tree
    static void findDepth(int node, int count,boolean visited[],List<Integer> nodes[]) {

        // If that particular node is visited it is marked as true in the boolean array named visted for the particular element
        visited[node] = true; 
        // The count variable is incremented by one value 
        count++; 
          
        // The depth of that particular node is found with the help of this findDepth() Function, and the deepest value is put into the maxCount variable

        List<Integer> l = nodes[node]; 
        for(Integer i: l) 
        { 
            if(!visited[i]){ 
                if (count >= maxCount) { 
                    maxCount = count; 
                    x = i; 
                } 
                findDepth(i, count, visited, nodes); 
            } 
        } 
    } 
       
    // A static Function named dfs is written to traverse the Binary Tree and then subsequently find the deepest element of that particular Binary Tree  
    
    // The dfs() Function has three parameters two of Integer type named node and n, and the third one is a List of Integer types named nodes representing the nodes of the binary tree
    static void dfs(int node, int n, List<Integer>nodes[]) { 

        // A boolean array named visted is created to keep track of all the nodes of the binary tree that are visited
        boolean[] visited = new boolean[n + 1]; 
        int count = 0; 
       
        // Initially, all the fields of the visited array is marked as false, representing that no node is visited at the beginning of the program
        Arrays.fill(visited, false); 
       
        // Then the deepest element of the binary tree is calculated that will be used to find the diameter of the binary tree 
        findDepth(node, count + 1, visited, nodes); 
          
    } 
       
    // A static Function named diameter is written to find the diameter of the binary tree 
    
    // The diameter() Function has two parameters one is a List of Integer types named nodes representing the nodes of the binary tree,, and the other is Integer named n
    static int diameter(List<Integer> nodes[], int n) 
    { 
        
        // the maxCount variable is initialised with the minimum value of the Integers
        maxCount = Integer.MIN_VALUE; 
       

        // Firstly, the deepest nodes that are present in the binary tree are found, and once the deepest nodes are found
        // Those will be used to find the diameter of the binary tree 
        dfs(1, n, nodes); 
       
        dfs(x, n, nodes); 
        
        return maxCount; 
    } 
       
    //The main Function is written to call the diameter() Function to get the diameter of the binary tree
    public static void main(String args[]) 
    { 
        int n = 5; 
       
        /* Constructed tree is 
             1 
            / \ 
            2    3 
           / \ 
          4   5 */

        // elements are added to the nodes of the binary tree
        nodes = new List[n + 1]; 
        for(int i = 0; i < n+1 ; i++) 
            nodes[i] = new ArrayList<Integer>();  
       
        /*create undirected edges */
        nodes[1].add(2); 
        nodes[2].add(1); 
        nodes[1].add(3); 
        nodes[3].add(1); 
        nodes[2].add(4); 
        nodes[4].add(2); 
        nodes[2].add(5); 
        nodes[5].add(2); 
          
        /* maxCount will have diameter of tree */
        int diametr = diameter(nodes,n);
        System.out.println("The Diameter of the given tree is " + diametr); 
    } // end of the main class
}// end of the Binary tree class

输出： 以上代码的输出为

The diameter of the given tree is 4

在上面的代码中，我们使用迭代方法计算了二叉树的直径。迭代方法中有重复的递归调用。在此方法中，空间和时间复杂度远低于递归方法。

查找二叉树直径的迭代方法的时间复杂度为 O(n)。

查找二叉树直径的迭代方法的空间复杂度为 O(n)。

下一主题二叉树的高度

二叉树的直径

查找二叉树直径的方法

1. 递归方法

2. 迭代方法

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

数据结构教程

DS 数组

DS 链表

DS 栈

DS 队列

DS 树

DS 图

DS 搜索

DS 排序

哈希与堆

差异

二叉树

二叉搜索树

AVL 树

单向链表

双向链表

循环链表

循环双向链表

DS 选择题

其他

二叉树的直径

查找二叉树直径的方法

1. 递归方法

2. 迭代方法

相关帖子

Recaman 序列

通用树 (N 元树)

DSA 中的无额外空间合并问题

在一个数组中实现两个栈

栈指针

给定一个 n x n 的方阵，查找大小为 k x k 的所有子正方形的和

程序以揭示扫雷中的位置

如果给出两种遍历序列，能否构建二叉树

使用多项式滚动哈希函数进行字符串哈希

查找每个经理下的员工数量

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器