Java代码实现在一颗三叉链表表示的二叉树中返回指定结点的所有祖先结点,并输出运行结果
时间: 2024-03-14 14:43:49 浏览: 217
下面是 Java 代码实现:
```java
public class AncestorsOfNodeInTernaryTree {
static class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode parent;
TreeNode(int val) {
this.val = val;
}
}
public static List<TreeNode> getAncestors(TreeNode root, TreeNode node) {
List<TreeNode> ancestors = new ArrayList<>();
while (node != null) {
ancestors.add(node);
node = node.parent;
}
Collections.reverse(ancestors);
return ancestors;
}
public static void main(String[] args) {
TreeNode root = new TreeNode(1);
root.left = new TreeNode(2);
root.middle = new TreeNode(3);
root.right = new TreeNode(4);
root.left.parent = root;
root.middle.parent = root;
root.right.parent = root;
root.left.left = new TreeNode(5);
root.left.middle = new TreeNode(6);
root.left.right = new TreeNode(7);
root.left.left.parent = root.left;
root.left.middle.parent = root.left;
root.left.right.parent = root.left;
TreeNode node = root.left.right;
List<TreeNode> ancestors = getAncestors(root, node);
for (TreeNode ancestor : ancestors) {
System.out.print(ancestor.val + " ");
}
// Output: 1 2 7
}
}
```
在这个实现中,我们定义了一个 `TreeNode` 类来表示三叉链表中的结点。`getAncestors` 方法接受根节点和目标结点作为参数,返回一个列表,其中包含目标结点的所有祖先结点。我们使用一个循环来遍历从目标结点到根节点的路径,并将每个结点添加到祖先列表中。最后,我们反转列表,以便列表中的结点以从根到目标结点的顺序排列。
在 `main` 方法中,我们创建了一个简单的三叉链表表示的二叉树,并调用 `getAncestors` 方法来查找结点 7 的所有祖先结点。输出结果为 1 2 7,这是从根节点到目标结点的路径上的所有结点。
阅读全文