Returns the maximum distance between two nodes of a binary tree

1、 subject

Given the root node of a binary tree root, There is a distance between any two nodes , Returns the maximum distance of the entire binary tree .

2、 analysis

The distance between two nodes is from A Node to B Number of nodes along the route .

There can be many solutions , But the binary tree routine ：

① The goal is ： With X In the case of root node , The maximum distance of the whole tree ;

② possibility ： May and X of , Maybe with X irrelevant .

• and X There are two possibilities for unrelated situations ：（1）X Maximum distance of left tree ;（2）X Maximum distance of right tree ;

• and X The possibility of the relevant situation ："X Left tree and X furthest + X Right tree and X furthest + 1“, and X Left tree and X The farthest is the height of the left tree ,X Right tree and X The farthest is the height of the right tree ,1 yes X node .

therefore , The information you want to get from the left tree and the right tree ：（1） The maximum distance of the tree ;（2） The height of the tree ;

The final result is to find the maximum of the three possibilities .

3、 Realization

C++ edition

/************************************************************************* > File Name: 037. Returns the maximum distance of a binary tree .cpp > Author: Maureen > Mail: [email protected] > Created Time:  5、 ... and  7/ 1 17:13:32 2022 ************************************************************************/

#include <iostream>
#include <ctime>
#include <unordered_map>
#include <unordered_set>
#include <vector>
using namespace std;

class TreeNode {
    
public:
    int value;
    TreeNode *left;
    TreeNode *right;

    TreeNode(int data) : value(data) {
    }
};

// Method 1 ： Violence enumeration , Preorder traversal obtains the sequence , Violently enumerate the distance between two nodes  
void fillPrelist(TreeNode *root, vector<TreeNode*> &arr) {
    
    if (root == nullptr) return ;

    arr.push_back(root);
    fillPrelist(root->left, arr);
    fillPrelist(root->right, arr);
}

vector<TreeNode *> getPrelist(TreeNode *root) {
    
    vector<TreeNode*> arr;
    fillPrelist(root, arr);
    return arr;
}
// Record the parent node of each node 
void fillParentMap(TreeNode *root, unordered_map<TreeNode*, TreeNode*> &parentMap) {
    
    if (root->left != nullptr) {
    
        parentMap[root->left] = root;
        fillParentMap(root->left, parentMap);
    }

    if (root->right != nullptr) {
    
        parentMap[root->right] = root;
        fillParentMap(root->right, parentMap);
    }
}

unordered_map<TreeNode *, TreeNode *> getParentMap(TreeNode *root) {
    
    unordered_map<TreeNode*, TreeNode*> _map;
    _map[root] = nullptr;
    fillParentMap(root, _map);
    return _map;
}


// Get the distance between two nodes 
int distance(unordered_map<TreeNode*, TreeNode*> &parentMap, TreeNode *o1, TreeNode *o2) {
    
    unordered_set<TreeNode*> o1set;
    TreeNode *cur = o1;
    o1set.insert(cur);

    while (parentMap[cur] != nullptr) {
    
        cur = parentMap[cur];
        o1set.insert(cur);
    }

	// find o1 and o2 The lowest common ancestor of 
    cur = o2;
    while (!o1set.count(cur)) {
    
        cur = parentMap[cur];
    }
	
	// Statistics o1 and o2 Distance to the lowest common ancestor 
    TreeNode *lowestAncestor = cur;
    cur = o1;
    int distance1 = 1;
    while (cur != lowestAncestor) {
    
        cur = parentMap[cur];
        distance1++;
    }

    cur = o2;
    int distance2 = 1;
    while (cur != lowestAncestor) {
    
        cur = parentMap[cur];
        distance2++;
    }
    
    return distance1 + distance2 - 1;
}

int maxDistance1(TreeNode *root) {
    
    if (root == nullptr) return 0;

    vector<TreeNode*> arr = getPrelist(root);

    unordered_map<TreeNode *, TreeNode *> parentMap = getParentMap(root);

    int ans = 0;
    for (int i = 0; i < arr.size(); i++) {
    
        for (int j = i; j < arr.size(); j++) {
    
            ans = max(ans, distance(parentMap, arr[i], arr[j]));
        }
    }
    return ans;
}

// Method 2  
class Info {
    
public:
    int maxDistance;
    int height;

    Info(int m, int h) {
    
        maxDistance = m;
        height = h;
    }
};


Info *process(TreeNode *x) {
    
    if (x == nullptr) {
    
        return new Info(0, 0);
    }

    Info *leftInfo = process(x->left);
    Info *rightInfo = process(x->right);

    int height = max(leftInfo->height, rightInfo->height) + 1;

    int p1 = leftInfo->maxDistance;
    int p2 = rightInfo->maxDistance;
    int p3 = leftInfo->height + rightInfo->height + 1;

    int maxDistance = max(max(p1, p2), p3);

    return new Info(maxDistance, height);
}

int maxDistance2(TreeNode *root) {
    
    return process(root)->maxDistance;
}


//for test
TreeNode *generate(int level, int maxl, int maxv) {
    
    if (level > maxl || (rand() % 100 / (double)101) < 0.5)
        return nullptr;

    TreeNode *root = new TreeNode(rand() % maxv);
    root->left = generate(level + 1, maxl, maxv);
    root->right = generate(level + 1, maxl, maxv);

    return root;
}

TreeNode *generateRandomBST(int level, int value) {
    
    return generate(1, level, value);
}

int main() {
    
    srand(time(0));

    int level = 5;
    int value = 100;
    int testTimes = 1000001;

    cout << "Test begin:" << endl;
    for (int i = 0; i < testTimes; i++) {
    
        TreeNode *root = generateRandomBST(level, value);
        if (maxDistance1(root) != maxDistance2(root)) {
    
            cout << "Failed!" << endl;
            return 0;
        }
        if (i && i % 100 == 0) cout << i << " cases passed!" << endl;
    }
    cout << "Success!" << endl;
    return 0;
}

Java edition

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;

import javax.security.auth.x500.X500PrivateCredential;

public class MaxDistance {
    
    public static class Node {
    
		public int value;
		public Node left;
		public Node right;

		public Node(int data) {
    
			this.value = data;
		}
	}

    // Method 1 ： Violence enumeration , Preorder traversal obtains the sequence , Violently enumerate the distance between two nodes 
	public static int maxDistance1(Node head) {
    
		if (head == null) {
    
			return 0;
		}
		ArrayList<Node> arr = getPrelist(head);
		HashMap<Node, Node> parentMap = getParentMap(head);
		int max = 0;
		for (int i = 0; i < arr.size(); i++) {
    
			for (int j = i; j < arr.size(); j++) {
    
				max = Math.max(max, distance(parentMap, arr.get(i), arr.get(j)));
			}
		}
		return max;
	}

	public static ArrayList<Node> getPrelist(Node head)
		ArrayList<Node> arr = new ArrayList<>();
		fillPrelist(head, arr);
		return arr;
	}

	public static void fillPrelist(Node head, ArrayList<Node> arr) {
    
		if (head == null) {
    
			return;
		}
		arr.add(head);
		fillPrelist(head.left, arr);
		fillPrelist(head.right, arr);
	}

	public static HashMap<Node, Node> getParentMap(Node head) {
    
		HashMap<Node, Node> map = new HashMap<>();
		map.put(head, null);
		fillParentMap(head, map);
		return map;
	}

	public static void fillParentMap(Node head, HashMap<Node, Node> parentMap) {
    
		if (head.left != null) {
    
			parentMap.put(head.left, head);
			fillParentMap(head.left, parentMap);
		}
		if (head.right != null) {
    
			parentMap.put(head.right, head);
			fillParentMap(head.right, parentMap);
		}
	}

	public static int distance(HashMap<Node, Node> parentMap, Node o1, Node o2) {
    
		HashSet<Node> o1Set = new HashSet<>();
		Node cur = o1;
		o1Set.add(cur);
		while (parentMap.get(cur) != null) {
    
			cur = parentMap.get(cur);
			o1Set.add(cur);
		}
		cur = o2;
		while (!o1Set.contains(cur)) {
    
			cur = parentMap.get(cur);
		}
		Node lowestAncestor = cur;
		cur = o1;
		int distance1 = 1;
		while (cur != lowestAncestor) {
    
			cur = parentMap.get(cur);
			distance1++;
		}
		cur = o2;
		int distance2 = 1;
		while (cur != lowestAncestor) {
    
			cur = parentMap.get(cur);
			distance2++;
		}
		return distance1 + distance2 - 1;
	}

    // Method 2 ： Recursive routine 
    public static int maxDistance2(Node head) {
    
        return process(head).maxDistance;
    }

    public static class Info {
    
        public int maxDistance; // The maximum distance of the tree 
        public int height; // The height of the tree 

        public Info(int m, int h) {
    
            this.maxDistance = m;
            this.height = h;
        }
    }

    // Be sure to return to Info, Otherwise, the subtree cannot be constrained 
    public static Info process(Node x) {
    
        // Empty tree distance is 0, The value is good to set 
        if (x == null) return new Info(0, 0);

        // Left tree information 
        Info leftInfo = process(x.left);

        // The information of the right tree 
        Info rightInfo = process(x.right);

        // Get the information of the current node according to the information of the left and right trees 
        // The height of the tree whose current node is root ：max( Left tree height , Right tree height ) + 1,1 It is the layer of the current node 
        int height = Math.max(leftInfo.height, rightInfo.height) + 1;

        // possibility 1： Not pass x node , Simply use the maximum distance of the left tree 
        int p1 = leftInfo.maxDistance;
        // possibility 2： Not pass x node , Simply use the maximum distance of the right tree 
        int p2 = rightInfo.maxDistance;
        // possibility 3： To pass x node , The height of the left tree  +  The height of the right tree  + 1（ own ）
        int p3 = leftInfo.height + rightInfo.height + 1;

        int maxDistance = Math.max(Math.max(p1, p2), p3);

        return new Info(maxDistance, height);
    }


    // Logarithmic apparatus 
    // for test
	public static Node generateRandomBST(int maxLevel, int maxValue) {
    
		return generate(1, maxLevel, maxValue);
	}

	// for test
	public static Node generate(int level, int maxLevel, int maxValue) {
    
		if (level > maxLevel || Math.random() < 0.5) {
    
			return null;
		}
		Node head = new Node((int) (Math.random() * maxValue));
		head.left = generate(level + 1, maxLevel, maxValue);
		head.right = generate(level + 1, maxLevel, maxValue);
		return head;
	}

	public static void main(String[] args) {
    
		int maxLevel = 4;
		int maxValue = 100;
		int testTimes = 1000000;
		for (int i = 0; i < testTimes; i++) {
    
			Node head = generateRandomBST(maxLevel, maxValue);
			if (maxDistance1(head) != maxDistance2(head)) {
    
				System.out.println("Oops!");
			}
		}
		System.out.println("finish!");
	}
}