题目
题目
思路
递归
- 最近公共祖先x满足：
x的左右子树分别包含p节点或q节点，或者x恰好是p节点或q节点且它的左子树或右子树有一个包含了另一个节点
class Solution {
private TreeNode ans = null;
private boolean dfs(TreeNode root, TreeNode p, TreeNode q) {
if (root == null) {
return false;
}
boolean lChild = dfs(root.left, p, q);
if (lChild && (root == p || root ==q)) {
ans = root;
return true;
}
boolean rChild = dfs(root.right, p ,q);
if (rChild && (root == p || root ==q)) {
ans = root;
return true;
}
if (lChild && rChild) {
ans = root;
return true;
}
return lChild || rChild || root == p || root ==q;
}
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
dfs(root, p, q);
return ans;
}
}
存储父节点
遍历二叉树使用哈希表存储所有节点的父节点，利用父节点信息从p节点开始不断往上跳，并记录已经访问过的节点，再从q节点开始不断往上跳，得到最先碰到的已经访问过的节点。
class Solution {
// <child, parent>
Map<TreeNode, TreeNode> parent = new HashMap<>();
Set<TreeNode> visited = new HashSet<>();
public void dfs(TreeNode root) {
if (root.left != null) {
parent.put(root.left, root);
dfs(root.left);
}
if (root.right != null) {
parent.put(root.right, root);
dfs(root.right);
}
}
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
dfs(root);
while (p != null) {
visited.add(p);
p = parent.get(p);
}
while (q != null) {
if (visited.contains(q)) {
return q;
}
q = parent.get(q);
}
return null;
}
}
