[Algorithm]Get Distance Between Two Nodes in Binary Tree

两个Node的距离取决于从node1到node2经过的edge数，如果考虑用类似LCA的解法的话，如果两个node的LCA是其中一个node，因为我们的算法不会再往下递归了，所以没法得到两者的距离。所以这里我们先计算LCA，之后算出node1和node2和LCA的depth，depth1 + depth2 - 2 * depthLCA就是最终的结果。找LCA的时间复杂度是O(n)，因为是binary tree，找depth的时间复杂度也是O(n)，所以总的时间复杂度是O(n)，代码如下：

	public class DistanceBetweenTwoNodes {
	public int getDistanace(TreeNode root, TreeNode node1, TreeNode node2) {
	if (root == null || node1 == null || node2 == null)
	return -1;
	TreeNode ancestor = LCA(root, node1, node2);
	int depth1 = getDepth(root, ancestor);
	int depth2 = getDepth(root, node1);
	int depth3 = getDepth(root, node2);
	return depth2 + depth3 - 2 * depth1;
	}
	private TreeNode LCA(TreeNode curr, TreeNode node1, TreeNode node2) {
	if (curr == null)
	return null;
	if (curr == node1 || curr == node2)
	return curr;
	TreeNode left = LCA(curr.left, node1, node2);
	TreeNode right = LCA(curr.right, node1, node2);
	if(left != null && right != null)
	return curr;
	return left == null? right: left;
	}
	private int getDepth(TreeNode curr, TreeNode target) {
	if (curr == null)
	return -1;
	if (curr == target)
	return 0;
	int left = getDepth(curr.left, target);
	int right = getDepth(curr.right, target);
	if (left == -1 && right == -1)
	return -1;
	return left == -1? right + 1: left + 1;
	}
	public static void main(String[] args) {
	test1();
	test2();
	test3();
	}
	//test cases
	private static void test1() {
	TreeNode root = new TreeNode(1);
	DistanceBetweenTwoNodes d = new DistanceBetweenTwoNodes();
	if (d.getDistanace(null, root, root) == -1 && d.getDistanace(root, root, root) == 0)
	System.out.println("Test case 1 passed!");
	else
	System.out.println("Test case 1 failed!");
	}
	private static void test2() {
	TreeNode root = new TreeNode(1);
	root.left = new TreeNode(2);
	root.right = new TreeNode(3);
	TreeNode node3 = new TreeNode(4);
	root.left.right = node3;
	root.left.left = new TreeNode(7);
	root.left.left.left = new TreeNode(10);
	root.right.right = new TreeNode(5);
	TreeNode node1 = new TreeNode(6);
	root.right.left = node1;
	root.right.right.right = new TreeNode(1);
	root.right.left.left = new TreeNode(-2);
	root.left.left.right = new TreeNode(-3);
	TreeNode node2 = new TreeNode(0);
	root.left.left.right.right = node2;
	DistanceBetweenTwoNodes d = new DistanceBetweenTwoNodes();
	if (d.getDistanace(root, node1, node1) == 0 && d.getDistanace(root, node1, node2) == 6
	&& d.getDistanace(root, node1, node3) == 4 && d.getDistanace(root, root, node2) == 4)
	System.out.println("Test case 2 passed!");
	else
	System.out.println("Test case 2 failed!");
	}
	private static void test3() {
	TreeNode root = new TreeNode(-3);
	root.left = new TreeNode(7);
	root.right = new TreeNode(-6);
	root.left.left = new TreeNode(4);
	root.left.right = new TreeNode(-2);
	TreeNode node1 = new TreeNode(5);
	root.right.right = node1;
	root.left.left.left = new TreeNode(12);
	root.left.left.left.right = new TreeNode(0);
	TreeNode node3 = new TreeNode(10);
	root.left.right.right = node3;
	root.right.right.left = new TreeNode(-8);
	TreeNode node2 = new TreeNode(-9);
	root.right.right.right = node2;
	TreeNode node4 = new TreeNode(17);
	root.right.right.left.left = node4;
	root.right.right.right.right= new TreeNode(-20);
	DistanceBetweenTwoNodes d = new DistanceBetweenTwoNodes();
	if (d.getDistanace(root, node1, node2) == 1 && d.getDistanace(root, node3, node4) == 7
	&& d.getDistanace(root, node4, node2) == 3 && d.getDistanace(root, root, node3) == 3)
	System.out.println("Test case 3 passed!");
	else
	System.out.println("Test case 3 failed!");
	}
	}

view raw distance between two nodes in binary tree.java hosted with ❤ by GitHub