每日算法之在二叉树中找到两个节点的最近公共祖先
JZ86 在二叉树中找到两个节点的最近公共祖先
题目
给定一棵二叉树(保证非空)以及这棵树上的两个节点对应的val值 o1 和 o2,请找到 o1 和 o2 的最近公共祖先节点。
注:本题保证二叉树中每个节点的val值均不相同。
方法 BFS,非递归方法
思路
算法实现
看到6和7公共祖先有5和3,但最近的是5。我们只要往上找,找到他们第一个相同的公共祖先节点即可,
但怎么找到每个节点的父节点呢,我们只需要把每个节点都遍历一遍,
然后顺便记录他们的父节点存储在Map中。我们先找到其中的一条路径,
比如6→5→3,然后在另一个节点往上找,由于7不在那条路径上,
我们找7的父节点是2,2也不在那条路径上,
我们接着往上找,2的父节点是5,5在那条路径上,所以5就是他们的最近公共子节点。
代码
package mid.JZ86在二叉树中找到两个节点的最近公共祖先;
import java.util.*;
class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
}
public class Solution {
/**
* @param root TreeNode类
* @param o1 int整型
* @param o2 int整型
* @return int整型
*/
public int lowestCommonAncestor(TreeNode root, int o1, int o2) {
// write code here
Queue<TreeNode> queue = new LinkedList<>();
//记录父节点
Map<Integer, Integer> parent = new HashMap<>();
parent.put(root.val, Integer.MIN_VALUE);
queue.add(root);
//BFS
while (!parent.containsKey(o1) || !parent.containsKey(o2)) {
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的所有祖先节点
while (parent.containsKey(o1)) {
ancestors.add(o1);
o1 = parent.get(o1);
}
while(!ancestors.contains(o2)) {
o2 = parent.get(o2);
}
return o2;
}
}