[Algorithm]Get Max Distance in Binary Tree

Distance定义为从一个节点到另一个节点经过的edge的数量，这一题其实跟max sum in bianry tree类似，返回左右子树的最深距离，然后相加看要不要更新返回值，然后去左和右的最大值加一return。代码如下：

	public class MaxDistanceInBinaryTree {
	private int dis = 0;
	public int getMaxDistance(TreeNode root) {
	getDistance(root);
	return dis;
	}
	private int getDistance(TreeNode root) {
	if(root == null)
	return 0;
	int left = getDistance(root.left);
	int right = getDistance(root.right);
	if(left + right > dis)
	dis = left + right;
	return left >= right? left + 1: right + 1;
	}
	public static void main(String[] args) {
	test1();
	test2();
	test3();
	}
	//test cases
	private static void test1() {
	TreeNode root = new TreeNode(1);
	MaxDistanceInBinaryTree m = new MaxDistanceInBinaryTree();
	if (m.getMaxDistance(null) == 0 && m.getMaxDistance(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);
	root.left.right = new TreeNode(4);
	root.left.left = new TreeNode(7);
	root.left.left.left = new TreeNode(10);
	root.right.right = new TreeNode(5);
	root.right.left = new TreeNode(6);
	root.right.right.right = new TreeNode(1);
	root.right.left.left = new TreeNode(-2);
	root.left.left.right = new TreeNode(-3);
	root.left.left.right.right = new TreeNode(0);
	MaxDistanceInBinaryTree m = new MaxDistanceInBinaryTree();
	if (m.getMaxDistance(root) == 7)
	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);
	root.right.right = new TreeNode(5);
	root.left.left.left = new TreeNode(12);
	root.left.left.left.right = new TreeNode(0);
	root.left.right.right = new TreeNode(10);
	root.right.right.left = new TreeNode(-8);
	root.right.right.right = new TreeNode(-9);
	root.right.right.left.left = new TreeNode(17);
	root.right.right.right.right= new TreeNode(-20);
	MaxDistanceInBinaryTree m = new MaxDistanceInBinaryTree();
	if (m.getMaxDistance(root) == 8)
	System.out.println("Test case 3 passed!");
	else
	System.out.println("Test case 3 failed!");
	}
	}

view raw get max distance in binary tree.java hosted with ❤ by GitHub

注意如果要返回距离最远的两个节点的话，就定义一个类，类里包含节点和深度两个变量，要更新距离的话，就把节点也更新一下。