剑指offer--树--树中两个结点的最低公共祖先
树中两个结点的最低公共祖先
问题（普通树）
求树中两个结点的最低公共祖先，此树不是二叉树，并且没有指向父节点的指针。
树的结点定义
private static class TreeNode {
int val;
List<TreeNode> children = new LinkedList<>();
public TreeNode() {
}
public TreeNode(int val) {
this.val = val;
}
@Override
public String toString() {
return val + "";
}
}
题目解析
假设还是输入结点F和H .
我们首先得到一条从根结点到树中某一结点的路径，这就要求在遍历的时候，有一个辅助内存来保存路径．比如我们用前序遍历的方法来得到从根结点到H 的路径的过程是这样的：
（ 1 ）遍历到A，把A 存放到路径中去，路径中只有一个结点A;
( 2 ）遍历到B，把B 存到路径中去，此时路径为A->B;
( 3 ）遍历到D，把D 存放到路径中去，此，时路径为A->B->D;
( 4 ） ：遍历到F，把F 存放到路径中去，此时路径为A->B->D->F;
( 5) F 已经没有子结点了，因此这条路径不可能到这结点H. 把F 从路径中删除，变成A->B->D;
( 6 ）遍历G. 和结点F 一样，这条路径也不能到达H. 边历完G 之后，路径仍然是A->B->D;
( 7 ）由于D 的所有子结点都遍历过了，不可能到这结点H，因此D 不在从A 到H 的路径中，把D 从路径中删除，变成A->B;
( 8 ）遥历E，把E 加入到路径中，此时路径变成A->B->E,
( 9 ）遍历H，已经到达目标给点， A->B->E 就是从根结点开始到达H 必须经过的路径。
同样，我们也可以得到从根结点开始到达F 必须经过的路径是A->B功。接着，我们求出这两个路径的最后公共结点，也就是B. B这个结点也是F 和H 的最低公共祖先．
为了得到从根结点开始到输入的两个结点的两条路径，需要追历两次树，每边历一次的时间复杂度是O(n）.得到的两条路径的长度在最差情况时是0（时，通常情况丁两条路径的长度是O(logn).
注意：可以在只遍历树一次就找到两个结点的路径，这部分留给读者自己去完成。
代码实现
public class Test1 {
public static void main(String[] args) {
test01();
System.out.println("==========");
test02();
System.out.println("==========");
test03();
}
// 形状普通的树
// 1
// / \
// 2 3
// / \
// 4 5
// / \ / | \
// 6 7 8 9 10
public static void test01() {
TreeNode n1 = new TreeNode(1);
TreeNode n2 = new TreeNode(2);
TreeNode n3 = new TreeNode(3);
TreeNode n4 = new TreeNode(4);
TreeNode n5 = new TreeNode(5);
TreeNode n6 = new TreeNode(6);
TreeNode n7 = new TreeNode(7);
TreeNode n8 = new TreeNode(8);
TreeNode n9 = new TreeNode(9);
TreeNode n10 = new TreeNode(10);
n1.children.add(n2);
n1.children.add(n3);
n2.children.add(n4);
n4.children.add(n6);
n4.children.add(n7);
n3.children.add(n5);
n5.children.add(n8);
n5.children.add(n9);
n5.children.add(n10);
System.out.println(getLastCommonParent(n1, n9, n10));
}
// 树退化成一个链表
// 1
// /
// 2
// /
// 3
// /
// 4
// /
// 5
private static void test02() {
TreeNode n1 = new TreeNode(1);
TreeNode n2 = new TreeNode(2);
TreeNode n3 = new TreeNode(3);
TreeNode n4 = new TreeNode(4);
TreeNode n5 = new TreeNode(5);
n1.children.add(n2);
n2.children.add(n3);
n3.children.add(n4);
n4.children.add(n5);
System.out.println(getLastCommonParent(n1, n4, n5));
}
// 树退化成一个链表，一个结点不在树中
// 1
// /
// 2
// /
// 3
// /
// 4
// /
// 5
private static void test03() {
TreeNode n1 = new TreeNode(1);
TreeNode n2 = new TreeNode(2);
TreeNode n3 = new TreeNode(3);
TreeNode n4 = new TreeNode(4);
TreeNode n5 = new TreeNode(5);
TreeNode n6 = new TreeNode(6);
n1.children.add(n2);
n2.children.add(n3);
n3.children.add(n4);
n4.children.add(n5);
System.out.println(getLastCommonParent(n1, n5, n6));
}
/*
* 获取两个节点的最低公共祖先
*/
public static TreeNode getLastCommonParent(TreeNode root, TreeNode p1, TreeNode p2) {
//path1和path2分别存储根节点到p1和p2的路径（不包括p1和p2）
List<TreeNode> path1 = new ArrayList<>();
List<TreeNode> path2 = new ArrayList<>();
List<TreeNode> tmpList = new ArrayList<>();
getNodePath(root, p1, tmpList, path1);
getNodePath(root, p2, tmpList, path2);
//如果路径不存在，返回空
if (path1.size() == 0 || path2.size() == 0)
{
return null;
}
return getLastCommonParent(path1, path2);
}
// 获取根节点到目标节点的路径
public static void getNodePath(TreeNode root, TreeNode target, List<TreeNode> tmpList, List<TreeNode> path) {
//鲁棒性
if (root == null || root == target)
{
return;
}
tmpList.add(root);
List<TreeNode> children = root.children;
for (TreeNode node : children) {
if (node == target) {
path.addAll(tmpList);
break;
}
getNodePath(node, target, tmpList, path);
}
tmpList.remove(tmpList.size() - 1);
}
//将问题转化为求链表最后一个共同节点
private static TreeNode getLastCommonParent(List<TreeNode> p1, List<TreeNode> p2) {
TreeNode tmpNode = null;
for (int i = 0; i < p1.size(); i++) {
if (p1.get(i) != p2.get(i))
{
break;
}
tmpNode = p1.get(i);
}
return tmpNode;
}
}
LeetCode
二叉搜索树的最近公共祖先
给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
例如，给定如下二叉搜索树: root = [6,2,8,0,4,7,9,null,null,3,5]
示例 1:
输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
输出: 6
解释: 节点 2 和节点 8 的最近公共祖先是 6。
示例 2:
输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
输出: 2
解释: 节点 2 和节点 4 的最近公共祖先是 2, 因为根据定义最近公共祖先节点可以为节点本身。
说明:
所有节点的值都是唯一的。
p、q 为不同节点且均存在于给定的二叉搜索树中。
public static void main(String[] args) {
TreeNode root = new TreeNode(6);
TreeNode treeNode1 = new TreeNode(2);
TreeNode treeNode2 = new TreeNode(8);
TreeNode treeNode3 = new TreeNode(0);
TreeNode treeNode4 = new TreeNode(4);
TreeNode treeNode5 = new TreeNode(7);
TreeNode treeNode6 = new TreeNode(9);
TreeNode treeNode7 = new TreeNode(3);
TreeNode treeNode8 = new TreeNode(5);
root.left = treeNode1;
root.right = treeNode2;
treeNode1.left = treeNode3;
treeNode1.right = treeNode4;
treeNode2.left = treeNode5;
treeNode2.right = treeNode6;
treeNode4.left = treeNode7;
treeNode4.right = treeNode8;
System.out.println(LowestCommonAncestor(root,treeNode7,treeNode8).val);
}
public static TreeNode LowestCommonAncestor(TreeNode root,TreeNode p,TreeNode q){
if(p== null|| q==null|| root==null){
return null;
}
//遍历左子树
if(p.val < root.val && q.val < root.val){
return LowestCommonAncestor(root.left,p,q);
}
//遍历右子树
if(p.val > root.val && q.val > root.val){
return LowestCommonAncestor(root.right,p,q);
}
//如果左边大于等于，右边小于等于，直接返回root
if(p.val <= root.val && q.val >= root.val){
return root;
}
return root;
}
二叉树的最近公共祖先
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
例如，给定如下二叉树: root = [3,5,1,6,2,0,8,null,null,7,4]
示例 1:
输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出: 3
解释: 节点 5 和节点 1 的最近公共祖先是节点 3。
示例 2:
输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出: 5
解释: 节点 5 和节点 4 的最近公共祖先是节点 5。因为根据定义最近公共祖先节点可以为节点本身。
说明:
所有节点的值都是唯一的。
p、q 为不同节点且均存在于给定的二叉树中。
思路：
从上往下遍历，判断根结点是否匹配两个节点之一，
如果是，则根结点就是最低祖先，否则往下递归遍历左右子树
如果两个节点在不同的左右子树，则根结点是最低祖先
如果两个节点都出现在左子树，则左节点为最低祖先
如果两个节点都出现在右子树，则右节点为最低祖先
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(root == null || root == q || root == p){
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 ? right : left;
}
}
public class Test2 {
/**
* 思路(非递归)：
* 1、找到root->p的路径
* 2、找到root->q的路径
* 3、两条路径求最后一个相交节点
*/
public static TreeNode lowestCommonAncestorII(TreeNode root, TreeNode p, TreeNode q) {
if (root == null || p == root || q == root) {
return root;
}
List<TreeNode> pPath = findPath(root, p);
List<TreeNode> qPath = findPath(root, q);
TreeNode common = null;
for (int i=0, j=0; i<pPath.size() && j<qPath.size(); i++,j++) {
if (pPath.get(i) == qPath.get(j)) {
common = pPath.get(i);
}
}
return common;
}
private static List<TreeNode> findPath(TreeNode root, TreeNode node) {
List<TreeNode> path = new ArrayList<>();
dfs(root, node, new ArrayList<>(), path);
return path;
}
private static void dfs(TreeNode root, TreeNode node, List<TreeNode> tmp, List<TreeNode> path) {
if (root == null) {
return;
}
tmp.add(root);
if (root == node) {
path.addAll(new ArrayList<>(tmp));
}
dfs(root.left, node, tmp, path);
dfs(root.right, node, tmp, path);
tmp.remove(tmp.size()-1);
}
public static void main(String[] args) {
TreeNode root = new TreeNode(1);
TreeNode right = new TreeNode(2);
root.right = right;
TreeNode left = new TreeNode(3);
root.left = left;
System.out.println(lowestCommonAncestorII(root, left, right).val);
}
}最深叶节点的最近公共祖先（未完待续）
给你一个有根节点的二叉树，找到它最深的叶节点的最近公共祖先。
回想一下：
叶节点 是二叉树中没有子节点的节点
树的根节点的 深度 为 0，如果某一节点的深度为 d，那它的子节点的深度就是 d+1
如果我们假定 A 是一组节点 S 的 最近公共祖先，<font color="#c7254e" face="Menlo, Monaco, Consolas, Courier New, monospace">S</font> 中的每个节点都在以 A 为根节点的子树中，且 A 的深度达到此条件下可能的最大值。
示例 1：
输入：root = [1,2,3]
输出：[1,2,3]
示例 2：
输入：root = [1,2,3,4]
输出：[4]
示例 3：
输入：root = [1,2,3,4,5]
输出：[2,4,5]
提示：
给你的树中将有 1 到 1000 个节点。
树中每个节点的值都在 1 到 1000 之间。
查看12道真题和解析
