FindtheDistancebetweenTwoNodesofaBinaryTree

题目：

find distance between two nodes in a binary tree.

题目分析：
这道题需要结合findLCA和annotate树来做。在这里可以装个b，先说找含有要找的值的node的depth，然后call findLCA，然后找LCA的depth，然后计算。之后说可以用annotation来优化。

代码：

public class FindtheDistancebetweenTwoNodesofaBinaryTree {

    static class Node {
        int data;
        Node left;
        Node right;
        int depth;
        int leftDepth;
        int rightDepth;

        public Node(int data) {
            this.data = data;
            this.left = null;
            this.right = null;
        }
    }
    public int findDistance(Node root, int n1, int n2) {
        Node rst = findLCA(root, n1, n2, 0);
        int leftDepth = rst.leftDepth;
        int rightDepth = rst.rightDepth;
        int currDepth = rst.depth;
        return leftDepth + rightDepth - 2 * currDepth + 1;
    }
    public Node findLCA(Node root, int n1, int n2, int depth) {
        if (root != null) {
            if (root.data == n1 || root.data == n2) {
                return root;
            }
            Node left = findLCA(root.left, n1, n2, depth + 1);
            Node right = findLCA(root.right, n1, n2, depth + 1);

            if (left != null && right != null) {
                root.leftDepth = left.depth;
                root.rightDepth = right.depth;
                root.depth = depth;
                return root;
            }
            if (left != null) {
                left.depth = depth;
                return left;
            }
            if (right != null) {
                right.depth = depth;
                return right;
            }
        }
        return null;
    }
    public static void main(String[] args) throws java.lang.Exception {
        Node root = new Node(5);
        root.left = new Node(10);
        root.right = new Node(15);
        root.left.left = new Node(20);
        root.left.right = new Node(25);
        root.right.left = new Node(30);
        root.right.right = new Node(35);
        root.left.right.right = new Node(45);
        FindtheDistancebetweenTwoNodesofaBinaryTree i = new FindtheDistancebetweenTwoNodesofaBinaryTree();
        System.out.println("Distance between 45 and 20 is : "                + i.findDistance(root, 45, 20));
    }
}