Java代码实现在一颗三叉链表表示的二叉树中返回两结点最近的共同祖先结点
时间: 2024-03-14 13:43:58 浏览: 67
可以使用递归的方法来实现在一颗三叉链表表示的二叉树中返回两结点最近的共同祖先结点。具体步骤如下:
1. 如果根节点为null或者p,q中有任意一个节点等于根节点,那么返回根节点。
2. 在左子树中查找p和q的最近共同祖先结点,如果返回值不为null,那么直接返回该值。
3. 在右子树中查找p和q的最近共同祖先结点,如果返回值不为null,那么直接返回该值。
4. 如果p和q分别在左子树和右子树中,那么当前节点就是它们的最近共同祖先结点,返回当前节点。
下面是Java代码实现:
```java
public class TreeNode {
int val;
TreeNode left, right, parent;
TreeNode(int val) {
this.val = val;
}
}
public class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root == null || p == root || q == root) {
return root;
}
TreeNode left = lowestCommonAncestor(root.left, p, q);
TreeNode right = lowestCommonAncestor(root.right, p, q);
if (left != null && right != null) {
return root;
}
return left != null ? left : right;
}
}
```
其中,TreeNode类表示三叉链表中的节点,包括左右子节点和父节点。Solution类中的lowestCommonAncestor方法即为查找p和q的最近共同祖先结点的方法。
阅读全文