剑指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 之间。