欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

剑指offer--树--树中两个结点的最低公共祖先

程序员文章站 2022-03-22 18:04:22
...

                           树中两个结点的最低公共祖先

问题(普通树)

求树中两个结点的最低公共祖先,此树不是二叉树,并且没有指向父节点的指针。

树的结点定义

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 .

剑指offer--树--树中两个结点的最低公共祖先

我们首先得到一条从根结点到树中某一结点的路径,这就要求在遍历的时候,有一个辅助内存来保存路径.比如我们用前序遍历的方法来得到从根结点到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]

 

剑指offer--树--树中两个结点的最低公共祖先

示例 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]

剑指offer--树--树中两个结点的最低公共祖先

示例 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 之间。