手撕真题-计算二叉树中两个节点之间的距离

思路

求解代码

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;
}
}