1、前言

题目描述：一棵二叉树 root，给定两个节点 p、q，求 p、q 之间的距离，也就是从 p 到 q 的距离。

2、思路

这道题是两年前实习的时候，才云科技问的题目（当时投的算法岗 QAQ），奈何当时基础很差，没答出来，也听不懂。

此题的思路是，先求两个节点的最近公共祖先，然后从最近公共祖先出发，求祖先节点到两个节点的距离，距离之和就是两个节点的最短路径。

3、代码

public class QB_ShortPath {


    public int shortPath(TreeNode root, TreeNode p, TreeNode q){
        TreeNode ans = lowestAns(root, p, q);

        int one = getPath(ans, p) - 1;
        int two = getPath(ans, q) - 1;

        return one + two;
    }

    /**
     * 求距离
     * @param root
     * @param target
     * @return
     */
    private int getPath(TreeNode root, TreeNode target) {
        if(root == null){
            return 0;
        }

        int left = getPath(root.left, target);
        int right = getPath(root.right, target);

        if(root == target){
            return 1;
        }

        if(left == 0 && right == 0){
            return 0;
        }

        return left == 0 ? right + 1 : left + 1;
    }

    /**
     * 求公共祖先
     * @param root
     * @param p
     * @param q
     * @return
     */
    private TreeNode lowestAns(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null || root == p || root == q){
            return root;
        }

        TreeNode left = lowestAns(root.left, p, q);
        TreeNode right = lowestAns(root.right, p, q);

        if(left == null && right == null){
            return null;
        }

        if(left == null){
            return right;
        }
        if(right == null){
            return left;
        }

        return root;
    }

    public static void main(String[] args) {
        TreeNode t1 = new TreeNode(1);
        TreeNode t2 = new TreeNode(2);
        TreeNode t3 = new TreeNode(3);
        TreeNode t4 = new TreeNode(4);
        TreeNode t5 = new TreeNode(5);
        TreeNode t6 = new TreeNode(6);
        TreeNode t7 = new TreeNode(7);
        TreeNode t8 = new TreeNode(8);

        t1.left = t2;
        t1.right = t3;
        t2.left = t4;
        t2.right = t5;
        t4.left = t6;
        t4.right = t7;
        t5.left = t8;

        System.out.println(new QB_ShortPath().shortPath(t1, t7, t3));
    }
}