Tree DP Maximum distance between nodes in a binary tree

This is the 28th day of my participation in the August Genwen Challenge

[question]

Starting from node A of the binary tree, you can go up or down, but the nodes along the path can only pass through once. The number of nodes on the path when you reach node B is called the distance from A to B. Then there is a distance between any two nodes of the binary tree.

【 答 案 】

Root = root; root = root; root = root

(1) The maximum value passes through the head node. In this case, the maximum distance is the distance from the node farthest from the head node in the left tree to the node farthest from the head node in the right tree. (2) This maximum value does not pass through the head node root, so the maximum distance is the largest distance between the left tree and the right tree.

2. Construct a class to represent the maximum distance of maxDistance and maximum height of H returned by the left and right subtrees in the recursive process

3. Recursively, compare the maximum distance between the left subtree and the maximum distance between the right subtree and the height of the left subtree + the height of the right subtree +1, and return the maximum value and the maximum value of H +1 in the left subtree and the right subtree.

public class TreeMaxDistance {
   
    /* The maximum distance between nodes in a binary tree can be calculated by starting from node A and walking up or down, but the nodes along the path can only pass through once. The number of nodes on the path when reaching node B is called the distance from A to B. Then there is a distance between any two nodes in the binary tree. * /
    public static ReturnData treeMaxDistance(Node root) {
        if (root == null) {
            return new ReturnData(0.0);
        }
        ReturnData leftData = treeMaxDistance(root.left);
        ReturnData rightData = treeMaxDistance(root.right);
        int max = leftData.h + rightData.h + 1;
        int max1 = leftData.maxDistance;
        int max2 = rightData.maxDistance;
        max = Math.max(Math.max(max1, max2), max);
        int h = Math.max(leftData.h, rightData.h);
        return new ReturnData(max, h + 1);  //h+1 is because we're adding the head of the tree
    }

    public static class ReturnData {
        int maxDistance;   // Indicates the maximum distance
        int h;  // Represents the height of the tree

        public ReturnData(int maxDistance, int h) {
            this.maxDistance = maxDistance;
            this.h = h; }}/ / node class
    public static class Node {
        int value;
        Node left;
        Node right;

        public Node(int value) {
            this.value = value; }}// Test the code
     public static void main(String[] args) {
        Node root = new Node(1);
        Node node2 = new Node(2);
        Node node3 = new Node(3);
        Node node4 = new Node(4);
        Node node5 = new Node(5);
        Node node8 = new Node(8);
        Node node9 = new Node(9);
        Node node10 = new Node(10);
        Node node11 = new Node(11);
        root.left = node2;
        root.right = node3;
        node2.left = node4;
        node2.right = node5;
        node4.left = node8;
        node8.left = node11;
        node5.right = node9;
        node9.right = node10;
        ReturnData returnData = treeMaxDistance(root);
        System.out.println("maxDistance="+ returnData.maxDistance); }}Copy the code