1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75

 public class TreeDistance {

        /**
         * 计算两个节点在二叉树中的距离
         *
         * @param root 二叉树的根节点
         * @param p    第一个节点
         * @param q    第二个节点
         * @return 两个节点之间的距离
         */
        public int distanceBetweenNodes(TreeNode root, TreeNode p, TreeNode q) {
            // 首先找到两个节点的最近公共祖先(LCA)
            TreeNode lca = findLCA(root, p, q);
            // 计算节点p到LCA的深度
            int depthP = findDepth(lca, p);
            // 计算节点q到LCA的深度
            int depthQ = findDepth(lca, q);
            // 两个节点之间的距离等于它们到LCA的深度之和
            return depthP + depthQ;
        }

        /**
         * 查找二叉树中两个节点的最近公共祖先(LCA)
         *
         * @param root 二叉树的根节点
         * @param p    第一个目标节点
         * @param q    第二个目标节点
         * @return 最近公共祖先节点，如果其中一个节点是根节点，则返回该节点；如果两个节点分别在左右子树中，则返回它们的根节点
         */
        private TreeNode findLCA(TreeNode root, TreeNode p, TreeNode q) {
            // 如果根节点为空，或者根节点是p或q中的一个，直接返回根节点
            if (root == null || root == p || root == q) {
                return root;
            }
            // 递归查找左子树中的LCA
            TreeNode left = findLCA(root.left, p, q);
            // 递归查找右子树中的LCA
            TreeNode right = findLCA(root.right, p, q);
            // 如果左右子树都找到了非空节点，说明p和q分别在左右子树中，当前节点就是LCA
            if (left != null && right != null) {
                return root;
            }
            // 如果左子树找到非空节点，则返回左子树的结果，否则返回右子树的结果
            return left != null ? left : right;
        }


        /**
         * 查找目标节点在给定祖先节点下的深度
         *
         * @param ancestor 起始祖先节点
         * @param target   目标节点
         * @return 目标节点相对于祖先节点的深度，如果未找到则返回-1
         */
        private int findDepth(TreeNode ancestor, TreeNode target) {
            // 如果祖先节点为空，说明无法找到目标节点，返回-1
            if (ancestor == null) {
                return -1;
            }
            // 如果当前节点就是目标节点，深度为0
            if (ancestor == target) {
                return 0;
            }
            // 递归查找左子树
            int left = findDepth(ancestor.left, target);
            // 如果在左子树中找到目标节点，返回左子树深度+1
            if (left != -1) {
                return left + 1;
            }
            // 递归查找右子树
            int right = findDepth(ancestor.right, target);
            // 如果在右子树中找到目标节点，返回右子树深度+1，否则返回-1
            return right != -1 ? right + 1 : -1;
        }
    }