在二叉树中找到两个节点的最近公共祖先（基于Java）

本文主要是介绍在二叉树中找到两个节点的最近公共祖先（基于Java），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

如题

 题解

    public int lowestCommonAncestor(TreeNode root, int o1, int o2) {//记录遍历到的每个节点的父节点。Map<Integer, Integer> parent = new HashMap<>();Queue<TreeNode> queue = new LinkedList<>();parent.put(root.val, Integer.MIN_VALUE);//根节点没有父节点，给他默认一个值queue.add(root);//直到两个节点都找到为止。while (!parent.containsKey(o1) || !parent.containsKey(o2)) {//队列是一边进一边出，这里poll方法是出队，TreeNode node = queue.poll();if (node.left != null) {//左子节点不为空，记录下他的父节点parent.put(node.left.val, node.val);//左子节点不为空，把它加入到队列中queue.add(node.left);}//右节点同上if (node.right != null) {parent.put(node.right.val, node.val);queue.add(node.right);}}Set<Integer> ancestors = new HashSet<>();//记录下o1和他的祖先节点，从o1节点开始一直到根节点。while (parent.containsKey(o1)) {ancestors.add(o1);o1 = parent.get(o1);}//前面得到了o1的祖先集合，之后看o1祖先集合中是否含o2，如果有那么答案就是o2，没有就不断// 去找o2的祖先，如果o2的祖先在o1祖先集合中，那么返回那个o2祖先while (!ancestors.contains(o2))o2 = parent.get(o2);return o2;}

Java中集合相关知识

• 队列：Queue<TreeNode> queue = new LinkedList<>();
• hashmap： Map<Integer, Integer> parent = new HashMap<>();
• 集合： Set<Integer> ancestors = new HashSet<>();
• 栈：Deque<Integer> stack = new ArrayDeque<>();

这篇关于在二叉树中找到两个节点的最近公共祖先（基于Java）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---