问：二叉树中查找最大距离节点的程序。

2025年3月17日 | 阅读16分钟

说明

在此程序中，我们需要找出二叉树中距离最大的节点。根据我们的方法，树中所有节点之间的所有距离都将存储在变量 distance 中。使用变量 MaxDistance 来存储最大值。最初，MaxDistance 初始化为 distance 的值。如果找到任何大于 MaxDistance 的值，则覆盖 MaxDistance 的值。

重复此过程，直到找到树中两个节点之间可能的最大距离。过程的算法如下。

Program to find the nodes which are at the maximum distance in a Binary Tree

算法

定义 Node 类，它有三个属性：data、left 和 right。其中，left 表示节点的左子节点，right 表示节点的右子节点。
创建节点时，将数据传递给节点的 data 属性，并将 left 和 right 都设置为 null。
定义另一个具有两个属性 root 和 treeArray 的类。
1. Root 表示树的根节点，并将其初始化为 null。
2. treeArray 将存储二叉树的数组表示。
nodesAtMaxDistance() 函数将找出位于最大距离处的节点。
1. 它将计算二叉树中所有节点之间的距离，并将其存储在变量 distance 中。
2. MaxDistance 用于跟踪节点之间的最大可能距离。如果 maxDistance 小于 distance，则 distance 的值将存储在 maxDistance 中。清除数组以清除先前存储的值。位于最大距离处的节点将存储在数组 arr 中。
3. 如果多个节点对位于最大距离处，则将它们存储在数组 arr 中。
calculateSize() 将计算树中的节点数。
convertBTtoArray() 函数将通过遍历树并将元素添加到 treeArray 来把二叉树转换为其数组表示。
getDistance() 函数将计算给定节点到根的距离。
LowestCommonAncestor() 函数将找出节点 n1 和 n2 的最近公共祖先。
1. 如果其中一个节点等于根节点，则返回根节点作为最近公共祖先。
2. 否则，在左子树和右子树中搜索节点 n1 和 n2。
3. 如果找到一个节点，该节点的左子节点是 n1，右子节点是 n2，反之亦然。则返回该节点作为最近公共祖先。
FindDistance() 函数将计算两个节点之间的距离。
1. 首先，它计算每个节点到根节点的距离。
2. 从该根节点中减去 2 * 最近公共祖先的距离。

解决方案

Python

#Represent a node of binary tree
class Node:
    def __init__(self,data):
        #Assign data to the new node, set left and right children to None
        self.data = data;
        self.left = None;
        self.right = None;
 
class MaxDistance:
    def __init__(self):
        #Represent the root of binary tree
        self.root = None;
        self.treeArray = [];
    
    #convertBTtoArray() will convert binary tree to its array representation    
    def convertBTtoArray(self, node):
        #Check whether tree is empty
        if(self.root == None):
            print("Tree is empty");
            return;
        else:
            if(node.left != None):
                self.convertBTtoArray(node.left);
            #Adds nodes of binary tree to treeArray
            self.treeArray.append(node.data); 
            if(node.right != None):
                self.convertBTtoArray(node.right);
                
    #getDistance() will find distance between root and a specific node
    def getDistance(self, temp, n1):
        if (temp != None):
            x = 0;
            #x will store the count of number of edges between temp and node n1
            if (temp.data == n1):
                return x + 1;
            x = self.getDistance(temp.left, n1);
            if(x > 0):
                return x + 1;
            x = self.getDistance(temp.right, n1);
            if(x > 0):
                return x + 1;
            return 0;
        return 0;
        
    #lowestCommonAncestor() will find out the lowest common ancestor for nodes node1 and node2
    def lowestCommonAncestor(self, temp, n1, n2):
        if (temp != None):
            #If root is equal to either of node node1 or node2, return root
            if (temp.data == n1 or temp.data == n2):
                return temp;
                
            #Traverse through left and right subtree
            left = self.lowestCommonAncestor(temp.left, n1, n2);
            right = self.lowestCommonAncestor(temp.right, n1, n2);
            
            #If node temp has one node(node1 or node2) as left child and one node(node1 or node2) as right child
            #Then, return node temp  as lowest common ancestor
            if (left != None and right != None):
                return temp;
            
            #If nodes node1 and node2 are in left subtree
            if (left != None):
                return left;
                
            #If nodes node1 and node2 are in right subtree
            if (right != None):
                return right;
                
        return None;
        
    #findDistance() will find distance between two given nodes
    def findDistance(self, node1, node2):
        #Calculates distance of first node from root
        d1 = self.getDistance(self.root, node1) - 1;
        #Calculates distance of second node from root
        d2 = self.getDistance(self.root, node2) - 1;
        
        #Calculates lowest common ancestor of both the nodes
        ancestor = self.lowestCommonAncestor(self.root, node1, node2);
        
        #If lowest common ancestor is other than root then, subtract 2 * (distance of root to ancestor)
        d3 = self.getDistance(self.root, ancestor.data) - 1;
        return (d1 + d2) - 2 * d3;
        
    #nodesAtMaxDistance() will display the nodes which are at maximum distance
    def nodesAtMaxDistance(self, node):
        maxDistance = 0;
        distance = 0;
        arr = [];
        
        #Convert binary tree to its array representation
        self.convertBTtoArray(node);
        
        for i in range(0, len(self.treeArray)):
            for j in range(i, len(self.treeArray)):
                #If distance is greater than maxDistance then, maxDistance will hold the value of distance
                distance = self.findDistance(self.treeArray[i], self.treeArray[j]);
                if(distance > maxDistance):
                    maxDistance = distance;
                    #Clear the arr
                    arr.clear();
                    #Add nodes at position i and j to treeArray
                    arr.append(self.treeArray[i]);
                    arr.append(self.treeArray[j]);
                
                #If more than one pair of nodes are at maxDistance then, add all pairs to treeArray    
                elif(distance == maxDistance):
                    arr.append(self.treeArray[i]);
                    arr.append(self.treeArray[j]);
                    
        #Display all pair of nodes which are at maximum distance            
        print("Nodes which are at maximum distance: ");
        for i in range(0, len(arr), 2):
            print("( " + str(arr[i]) + "," + str(arr[i+1]) + " )");
            
bt = MaxDistance();
#Add nodes to the binary tree
bt.root = Node(1);
bt.root.left = Node(2);
bt.root.right = Node(3);
bt.root.left.left = Node(4);
bt.root.left.right = Node(5);
bt.root.right.left = Node(6);
bt.root.right.right = Node(7);
bt.root.right.right.right = Node(8);
bt.root.right.right.right.left = Node(9);
 
#Finds out all the pair of nodes which are at maximum distance
bt.nodesAtMaxDistance(bt.root);

输出

Nodes which are at maximum distance: 
( 4,9 )
( 5,9 )

C

#include <stdio.h>
#include <stdlib.h>
#include <memory.h>
 
//Represent a node of binary tree
struct node{
    int data;
    struct node *left;
    struct node *right;
};
 
//Represent the root of binary tree
struct node *root = NULL;
 
int treeArray[50];
int index = 0;
    
//createNode() will create a new node
struct node* createNode(int data){
    //Create a new node
    struct node *newNode = (struct node*)malloc(sizeof(struct node));
    //Assign data to newNode, set left and right children to NULL
    newNode->data = data;
    newNode->left = NULL;
    newNode->right = NULL;
    
    return newNode;
}
 
//calculateSize() will calculate size of tree
int calculateSize(struct node *node)
{    
    int size = 0;
    if (node == NULL)
     return 0;
    else {
        size = calculateSize (node->left) + calculateSize (node->right) + 1;
        return size;
    }
}
 
//convertBTtoArray() will convert binary tree to its array representation
void convertBTtoArray(struct node *node) {
    //Check whether tree is empty
    if(root == NULL){
        printf("Tree is empty\n");
        return;
    }
    else {
        if(node->left != NULL)
            convertBTtoArray(node->left);
        //Adds nodes of binary tree to treeArray
        treeArray[index] = node->data; 
        index++;
        if(node->right != NULL)
            convertBTtoArray(node->right);  
        }      
}
 
//getDistance() will find distance between root and a specific node
int getDistance(struct node *temp, int n1) {
    if (temp != NULL) {
        int x = 0;
        if ((temp->data == n1) || (x = getDistance(temp->left, n1)) > 0
                || (x = getDistance(temp->right, n1)) > 0) {
            //x will store the count of number of edges between temp and node n1
            return x + 1;
        }
        return 0;
    }
    return 0;
}
 
//lowestCommonAncestor() will find out the lowest common ancestor for nodes node1 and node2
struct node* lowestCommonAncestor(struct node *temp, int node1, int node2) {
    if (temp != NULL) {
        //If root is equal to either of node node1 or node2, return root
        if (temp->data == node1 || temp->data == node2) {
            return temp;
        }
        
        //Traverse through left and right subtree
        struct node *left = lowestCommonAncestor(temp->left, node1, node2);
        struct node *right = lowestCommonAncestor(temp->right, node1, node2);
        
        //If node temp has one node(node1 or node2) as left child and one node(node1 or node2) as right child
        //Then, return node temp  as lowest common ancestor
        if (left != NULL && right != NULL) {
            return temp;
        }
        
        //If nodes node1 and node2 are in left subtree
        if (left != NULL) {
            return left;
        }
        //If nodes node1 and node2 are in right subtree
        if (right != NULL) {
            return right;
        }
    }
    return NULL;
}
 
//findDistance() will find distance between two given nodes
int findDistance(int node1, int node2) {
    //Calculates distance of first node from root
    int d1 = getDistance(root, node1) - 1;
    //Calculates distance of second node from root
    int d2 = getDistance(root, node2) - 1;
    
    //Calculates lowest common ancestor of both the nodes
    struct node *ancestor = lowestCommonAncestor(root, node1, node2);
    
    //If lowest common ancestor is other than root then, subtract 2 * (distance of root to ancestor)
    int d3 = getDistance(root, ancestor->data) - 1;
    return (d1 + d2) - 2 * d3;
}
 
//nodesAtMaxDistance() will display the nodes which are at maximum distance
void nodesAtMaxDistance(struct node *node) {
    int maxDistance = 0, distance = 0, counter = 0;
    int arr[50];
            
    //Length of treeArray
    int treeSize = calculateSize(node);
    
    //Convert binary tree to its array representation
    convertBTtoArray(node);
 
    //Calculates distance between all the nodes present in binary tree and stores maximum distance in variable maxDistance
    for(int i = 0; i < treeSize; i++) {
        for(int j = i; j < treeSize; j++) {
            distance = findDistance(treeArray[i], treeArray[j]);
            //If distance is greater than maxDistance then, maxDistance will hold the value of distance
            if(distance > maxDistance) {
                maxDistance = distance;
                //Clear the arr
                memset(arr, 0, sizeof(arr));
                //Add nodes at position i and j to treeArray
                arr[counter++] = treeArray[i];
                arr[counter++] = treeArray[j];
            }
            //If more than one pair of nodes are at maxDistance then, add all pairs to treeArray
            else if(distance == maxDistance) {
                arr[counter++] = treeArray[i];
                arr[counter++] = treeArray[j];
            }
        }    
    }
    int length = sizeof(arr)/sizeof(arr[0]);
    //Display all pair of nodes which are at maximum distance
    printf("Nodes which are at maximum distance: ");
    for(int i = 0; i < length; i = i + 2) {
        if(arr[i] != 0 && arr[i+1] != 0)
            printf("\n( %d,%d )", arr[i], arr[i+1]);
    }
}
    
int main()
{
    //Add nodes to the binary tree
    root = createNode(1);
    root->left = createNode(2);
    root->right = createNode(3);
    root->left->left = createNode(4);
    root->left->right = createNode(5);
    root->right->left = createNode(6);
    root->right->right = createNode(7);
    root->right->right->right = createNode(8);
    root->right->right->right->left = createNode(9);
    
    //Finds out all the pair of nodes which are at maximum distance
    nodesAtMaxDistance(root);
    
    return 0;
} 

输出

Nodes which are at maximum distance: 
( 4,9 )
( 5,9 )

JAVA

import java.util.ArrayList;
 
public class MaxDistance {
    
    //Represent a node of binary tree
    public static class Node{
        int data;
        Node left;
        Node right;
        
        public Node(int data){
            //Assign data to the new node, set left and right children to null
            this.data = data;
            this.left = null;
            this.right = null;
            }
          }
          
    //Represent the root of binary tree
    public Node root;
    
    int[] treeArray;
    int index = 0;
    
    public MaxDistance(){
        root = null;
    }
    
    //calculateSize() will calculate size of tree
    public int calculateSize(Node node)
    {    
        int size = 0;
        if (node == null)
         return 0;
        else {
            size = calculateSize (node.left) + calculateSize (node.right) + 1;
            return size;
        }
    }
    
    //convertBTtoArray() will convert binary tree to its array representation
    public void convertBTtoArray(Node node) {
        //Check whether tree is empty
        if(root == null){
            System.out.println("Tree is empty");
            return;
        }
        else {
            if(node.left != null)
                convertBTtoArray(node.left);
            //Adds nodes of binary tree to treeArray
            treeArray[index] = node.data; 
            index++;
            if(node.right != null)
                convertBTtoArray(node.right);  
            }      
    }
    
    //getDistance() will find distance between root and a specific node
    public int getDistance(Node temp, int n1) {
        if (temp != null) {
            int x = 0;
            if ((temp.data == n1) || (x = getDistance(temp.left, n1)) > 0
                    || (x = getDistance(temp.right, n1)) > 0) {
                //x will store the count of number of edges between temp and node n1
                return x + 1;
            }
            return 0;
        }
        return 0;
    }
    
    //lowestCommonAncestor() will find out the lowest common ancestor for nodes node1 and node2
    public Node lowestCommonAncestor(Node temp, int node1, int node2) {
        if (temp != null) {
            //If root is equal to either of node node1 or node2, return root
            if (temp.data == node1 || temp.data == node2) {
                return temp;
            }
            
            //Traverse through left and right subtree
            Node left = lowestCommonAncestor(temp.left, node1, node2);
            Node right = lowestCommonAncestor(temp.right, node1, node2);
            
            //If node temp has one node(node1 or node2) as left child and one node(node1 or node2) as right child
            //Then, return node temp  as lowest common ancestor
            if (left != null && right != null) {
                return temp;
            }
            
            //If nodes node1 and node2 are in left subtree
            if (left != null) {
                return left;
            }
            //If nodes node1 and node2 are in right subtree
            if (right != null) {
                return right;
            }
        }
        return null;
    }    
    
    //findDistance() will find distance between two given nodes
    public int findDistance(int node1, int node2) {
        //Calculates distance of first node from root
        int d1 = getDistance(root, node1) - 1;
        //Calculates distance of second node from root
        int d2 = getDistance(root, node2) - 1;
        
        //Calculates lowest common ancestor of both the nodes
        Node ancestor = lowestCommonAncestor(root, node1, node2);
        
        //If lowest common ancestor is other than root then, subtract 2 * (distance of root to ancestor)
        int d3 = getDistance(root, ancestor.data) - 1;
        return (d1 + d2) - 2 * d3;
    }
    
    //nodesAtMaxDistance() will display the nodes which are at maximum distance
    public void nodesAtMaxDistance(Node node) {
        int maxDistance = 0, distance = 0;
        ArrayList<Integer> arr = new ArrayList<>();
                
        //Initialize treeArray
        int treeSize = calculateSize(node);
        treeArray = new int[treeSize];
        
        //Convert binary tree to its array representation
        convertBTtoArray(node);
 
        //Calculates distance between all the nodes present in binary tree and stores maximum distance in variable maxDistance
        for(int i = 0; i < treeArray.length; i++) {
            for(int j = i; j < treeArray.length; j++) {
                distance = findDistance(treeArray[i], treeArray[j]);
                //If distance is greater than maxDistance then, maxDistance will hold the value of distance
                if(distance > maxDistance) {
                    maxDistance = distance;
                    arr.clear();
                    //Add nodes at position i and j to treeArray
                    arr.add(treeArray[i]);
                    arr.add(treeArray[j]);
                }
                //If more than one pair of nodes are at maxDistance then, add all pairs to treeArray
                else if(distance == maxDistance) {
                    arr.add(treeArray[i]);
                    arr.add(treeArray[j]);
                }
            }    
        }
        //Display all pair of nodes which are at maximum distance
        System.out.println("Nodes which are at maximum distance: ");
        for(int i = 0; i < arr.size(); i = i + 2) {
            System.out.println("( " + arr.get(i) + "," + arr.get(i+1) + " )");
        }
    }
    
    public static void main(String[] args) {
        
        MaxDistance bt = new MaxDistance();
        //Add nodes to the binary tree
        bt.root = new Node(1);
        bt.root.left = new Node(2);
        bt.root.right = new Node(3);
        bt.root.left.left = new Node(4);
        bt.root.left.right = new Node(5);
        bt.root.right.left = new Node(6);
        bt.root.right.right = new Node(7);
        bt.root.right.right.right = new Node(8);
        bt.root.right.right.right.left = new Node(9);
        
        //Finds out all the pair of nodes which are at maximum distance
        bt.nodesAtMaxDistance(bt.root);
      }
}

输出

Nodes which are at maximum distance: 
( 4,9 )
( 5,9 )

C#

using System;
using System.Collections;
namespace Tree 
{                     
    public class Program
    {
        //Represent a node of binary tree
        public class Node<T>{
            public T data;
            public Node<T> left;
            public Node<T> right;
            
            public Node(T data) {
                //Assign data to the new node, set left and right children to null
                this.data = data;
                this.left = null;
                this.right = null;
            }
        }
        
        public class MaxDistance<T>{
            //Represent the root of binary tree
            public Node<T> root;
            
            T[] treeArray;
            int index = 0;
            
            public MaxDistance(){
                root = null;
            }
            
            //calculateSize() will calculate size of tree
            int calculateSize(Node<T> node)
            {    
                int size = 0;
                if (node == null)
                 return 0;
                else {
                    size = calculateSize (node.left) + calculateSize (node.right) + 1;
                    return size;
                }
            }
            
            //convertBTtoArray() will convert the given binary tree to its corresponding array representation
            public void convertBTtoArray(Node<T> node) {
                //Check whether tree is empty
                if(root == null){
                    Console.WriteLine("Tree is empty");
                    return;
                }
                else {
                    if(node.left!= null)
                        convertBTtoArray(node.left);
                    //Adds nodes of binary tree to treeArray
                    treeArray[index] = node.data; 
                    index++;
                    if(node.right!= null)
                        convertBTtoArray(node.right);  
                    }      
                }
            
            //getDistance() will find distance between root and a specific node
            public int getDistance(Node<T> temp, T n1) {
                if (temp != null) {
                    int x = 0;
                    if ((temp.data.Equals(n1)) || (x = getDistance(temp.left, n1)) > 0
                            || (x = getDistance(temp.right, n1)) > 0) {
                        //x will store the count of number of edges between temp and node n1
                        return x + 1;
                    }
                    return 0;
                }
                return 0;
            }
            
            //lowestCommonAncestor() will find out the lowest common ancestor for nodes node1 and node2
            public Node<T> lowestCommonAncestor(Node<T> temp, T n1, T n2) {
                if (temp != null) {
                    //If root is equal to either of node node1 or node2, return root
                    if (temp.data.Equals(n1) || temp.data.Equals(n2)) {
                        return temp;
                    }
                    //Traverse through left and right subtree
                    Node<T> left = lowestCommonAncestor(temp.left, n1, n2);
                    Node<T> right = lowestCommonAncestor(temp.right, n1, n2);
                    
                    //If node temp has one node(node1 or node2) as left child and one node(node1 or node2) as right child
                    //Then, return node temp  as lowest common ancestor
                    if (left != null && right != null) {
                        return temp;
                    }
                    //If nodes node1 and node2 are in left subtree
                    if (left != null) {
                        return left;
                    }
                    //If nodes node1 and node2 are in right subtree
                    if (right != null) {
                        return right;
                    }
                }
                return null;
            }
            
            //findDistance() will find distance between two given nodes
            public int findDistance(T node1, T node2) {
                //Calculates distance of first node from root
                int d1 = getDistance(root, node1) - 1;
                //Calculates distance of second node from root
                int d2 = getDistance(root, node2) - 1;
                
                //Calculates lowest common ancestor of both the nodes
                Node<T> ancestor = lowestCommonAncestor(root, node1, node2);
                
                //If lowest common ancestor is other than root then, subtract 2 * (distance of root to ancestor)
                int d3 = getDistance(root, ancestor.data) - 1;
                return (d1 + d2) - 2 * d3;
            }
            
            //nodesAtMaxDistance() will display the nodes which are at maximum distance
            public void nodesAtMaxDistance(Node<T> node) {
                int maxDistance = 0, distance = 0;
                ArrayList arr = new ArrayList();
                        
                //Initialize treeArray
                int treeSize = calculateSize(node);
                treeArray = new T[treeSize];
                
                //Convert binary tree to its array representation
                convertBTtoArray(node);
                
                //Calculates distance between all the nodes present in binary tree and stores maximum distance in variable maxDistance
                for(int i = 0; i < treeArray.Length; i++) {
                    for(int j = i; j < treeArray.Length; j++) {
                        distance = findDistance(treeArray[i], treeArray[j]);
                        //If distance is greater than maxDistance then, maxDistance will hold the value of distance
                        if(distance > maxDistance) {
                            maxDistance = distance;
                            arr.Clear();
                            //Add nodes at position i and j to treeArray
                            arr.Add(treeArray[i]);
                            arr.Add(treeArray[j]);
                        }
                        //If more than one pair of nodes are at maxDistance then, add all pairs to treeArray
                        else if(distance == maxDistance) {
                            arr.Add(treeArray[i]);
                            arr.Add(treeArray[j]);
                        }
                    }    
                }
                //Display all pair of nodes which are at maximum distance
                Console.WriteLine("Nodes which are at maximum distance: ");
                for(int i = 0; i < arr.Count; i = i + 2) {
                    Console.WriteLine("( " + arr[i] + "," + arr[i+1] + " )");
                }
            }
            }
        
        public static void Main()
        {
            MaxDistance<int> bt = new MaxDistance<int>();
            //Add nodes to the binary tree
            bt.root = new Node<int>(1);
            bt.root.left = new Node<int>(2);
            bt.root.right = new Node<int>(3);
            bt.root.left.left = new Node<int>(4);
            bt.root.left.right = new Node<int>(5);
            bt.root.right.left = new Node<int>(6);
            bt.root.right.right = new Node<int>(7);
            bt.root.right.right.right = new Node<int>(8);
            bt.root.right.right.right.left = new Node<int>(9);
            
            //Finds out all the pair of nodes which are at maximum distance
            bt.nodesAtMaxDistance(bt.root);                
        }    
    }
}

输出

Nodes which are at maximum distance: 
( 4,9 )
( 5,9 )

PHP

<!DOCTYPE html>
<html>
<body>
<?php
//Represent a node of binary tree
class Node{
    public $data;
    public $left;
    public $right;
    
    function __construct($data){
        //Assign data to the new node, set left and right children to NULL
        $this->data = $data;
        $this->left = NULL;
        $this->right = NULL;
    }
}
class MaxDistance{
    //Represent the root of binary tree
    public $root;
    public $treeArray;
    function __construct(){
        $this->root = NULL;
        $this->treeArray = array();
    }
    
    //convertBTtoArray() will convert binary tree to its array representation
    function convertBTtoArray($node) {
        //Check whether tree is empty
        if($this->root == NULL){
            print("Tree is empty <br>");
            return;
        }
        else {
            if($node->left != NULL)
                $this->convertBTtoArray($node->left);
            //Adds nodes of binary tree to treeArray
            array_push($this->treeArray, $node->data); 
            if($node->right != NULL)
                $this->convertBTtoArray($node->right);  
            }      
    }
    
    //getDistance() will find distance between root and a specific node
    function getDistance($temp, $n1){
        if ($temp != NULL) {
            $x = 0;
            if (($temp->data == $n1) || ($x = $this->getDistance($temp->left, $n1)) > 0
                    || ($x = $this->getDistance($temp->right, $n1)) > 0) {
                //x will store the count of number of edges between temp and node n1
                return $x + 1;
            }
            return 0;
        }
        return 0;
    }
    
    //lowestCommonAncestor() will find out the lowest common ancestor for nodes node1 and node2
    function lowestCommonAncestor($temp, $node1, $node2) {
        if ($temp != NULL) {
            //If root is equal to either of node node1 or node2, return root
            if ($temp->data == $node1 || $temp->data == $node2) {
                return $temp;
            }
            
            //Traverse through left and right subtree
            $left = $this->lowestCommonAncestor($temp->left, $node1, $node2);
            $right = $this->lowestCommonAncestor($temp->right, $node1, $node2);
            
            //If node temp has one node(node1 or node2) as left child and one node(node1 or node2) as right child
            //Then, return node temp  as lowest common ancestor
            if ($left != NULL && $right != NULL) {
                return $temp;
            }
            
            //If nodes node1 and node2 are in left subtree
            if ($left != NULL) {
                return $left;
            }
            //If nodes node1 and node2 are in right subtree
            if ($right != NULL) {
                return $right;
            }
        }
        return NULL;
    }    
    
    //findDistance() will find distance between two given nodes
    function findDistance($node1, $node2) {
        //Calculates distance of first node from root
        $d1 = $this->getDistance($this->root, $node1) - 1;
        //Calculates distance of second node from root
        $d2 = $this->getDistance($this->root, $node2) - 1;
        
        //Calculates lowest common ancestor of both the nodes
        $ancestor = $this->lowestCommonAncestor($this->root, $node1, $node2);
        
        //If lowest common ancestor is other than root then, subtract 2 * (distance of root to ancestor)
        $d3 = $this->getDistance($this->root, $ancestor->data) - 1;
        return ($d1 + $d2) - 2 * $d3;
    }
    
    //nodesAtMaxDistance() will display the nodes which are at maximum distance
    function nodesAtMaxDistance($node) {
        $maxDistance = 0;
        $distance = 0;
        $arr = array();
        
        //Convert binary tree to its array representation
        $this->convertBTtoArray($node);
 
        //Calculates distance between all the nodes present in binary tree and stores maximum distance in variable maxDistance
        for($i = 0; $i < count($this->treeArray); $i++) {
            for($j = $i; $j < count($this->treeArray); $j++) {
                $distance = $this->findDistance($this->treeArray[$i], $this->treeArray[$j]);
                //If distance is greater than maxDistance then, maxDistance will hold the value of distance
                if($distance > $maxDistance) {
                    $maxDistance = $distance;
                    $arr = array();
                    //Add nodes at position i and j to treeArray
                    array_push($arr, $this->treeArray[$i]);
                    array_push($arr, $this->treeArray[$j]);
                }
                //If more than one pair of nodes are at maxDistance then, add all pairs to treeArray
                else if($distance == $maxDistance) {
                    array_push($arr, $this->treeArray[$i]);
                    array_push($arr, $this->treeArray[$j]);
                }
            }    
        }
        //Display all pair of nodes which are at maximum distance
        print("Nodes which are at maximum distance: <br>");
        for($i = 0; $i < sizeof($arr); $i = $i + 2) {
            print("( " . $arr[$i] . "," . $arr[$i+1] . " )");
            print("<br>");
        }
    }    
}
    
$bt = new MaxDistance();
//Add nodes to the binary tree
$bt->root= new Node(1);
$bt->root->left = new Node(2);
$bt->root->right = new Node(3);
$bt->root->left->left = new Node(4);
$bt->root->left->right = new Node(5);
$bt->root->right->left = new Node(6);
$bt->root->right->right = new Node(7);
$bt->root->right->right->right = new Node(8);
$bt->root->right->right->right->left = new Node(9);
 
//Finds out all the pair of nodes which are at maximum distance
$bt->nodesAtMaxDistance($bt->root);      
?>
</body>
</html> 

输出

Nodes which are at maximum distance: 
( 4,9 )
( 5,9 )

下一个主题程序列表

问：二叉树中查找最大距离节点的程序。

说明

算法

解决方案

Python

C

JAVA

C#

PHP

联系信息

关注我们

教程

面试题

在线编译器

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

程序

问：二叉树中查找最大距离节点的程序。

说明

算法

解决方案

Python

C

JAVA

C#

PHP

相关帖子

将厘米转换为米的程序

打印 1 到 100 之间的所有迪沙里数的程序

在双向链表末尾插入新节点的程序

不使用第三个变量交换两个数字的程序

以升序对数组元素进行排序的程序

计算字符串中单词总数的程序

查找半圆面积和周长的程序

将字符串中的空格替换为特定字符的程序

从单向链表末尾删除节点的程序

从单链表中查找最大值和最小值节点的程序

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器