题解 | #在二叉树中找到两个节点的最近公共祖先#

在二叉树中找到两个节点的最近公共祖先

http://www.nowcoder.com/practice/e0cc33a83afe4530bcec46eba3325116

题目描述: 题目要求简单易懂,就是在一棵二叉树中找到给定的o1和o2这两个节点的最近的公共祖先。

我们想想,两个节点的最近的公共祖先,无外乎就以下几种情况。
第一种,o1和o2恰好分布在根节点root的两侧,那么最近的公共祖先即为根节点root。
图片说明

第二种,o1和o2分布在根节点的同一侧,那么则会出现两种情况。

① 首先,出现如下图这种情况,则可以转变为第一种情况,o1和o2分布在了值为5的这个节点的两侧。那么此时o1和o2的最近公共祖先则为值为5这个节点。
情况1

② o1和o2恰好的父子节点的关系,那么此时它们最近的公共祖先则为那个父节点的节点。
图片说明

所以,基于上面情况的分析,我们可以使用递归的方式来解决这道题目。

方法一:递归
直接从根节点往下寻找,如果当前节点既不是o1也不是o2。

  • 从左侧寻找o1和o2,当找到其中一个则返回
  • 从右侧寻找o1和o2,当找到其中一个则返回
    如果当前节点为o1或者o2,则证明当前节点为两者的最近公共祖先。

    例如,当前节点是o1,那么此时o2必定是o1的子孙节点。所以o1即为两者的最近公共祖先。

代码:

public int lowestCommonAncestor (TreeNode root, int o1, int o2) {
        // write code here
        return LRD(root,o1,o2).val;
    }

    public TreeNode LRD(TreeNode root, int o1, int o2){
        // 找到o1或者o2,或者遍历到尽头还没找到则返回root(null)
        if(root == null || root.val == o1 || root.val == o2)
            return root;
        // 朝着root节点的左边去寻找o1,o2
        TreeNode left = LRD(root.left,o1,o2);
        // 朝着root节点的右边去寻找o1,o2
        TreeNode right = LRD(root.right,o1,o2);

        // 如果root节点的左边没有o1或者o2,则证明o1和o2分布在二叉树的右侧
        // 那么此时则直接返回right, right为先找到的节点 o1或者o2
        if(left == null)
            return right;
        // 如果root节点的右边没有o1或者o2,则证明o1和o2分布在二叉树的左侧
        // 那么此时则直接返回left, left为先找到的节点 o1或者o2
        if(right == null)
            return left;

        // 否则,当前节点即为o1和o2的最近公共祖先,此时o1和o2分布在root两侧
        return root;
    }

复杂度分析:
时间复杂度:。n为二叉树的结点数,需要遍历n次。
空间复杂度:。当二叉树退化成链表的时候,此时递归深度为n。

方法二:使用哈希表存储父节点
我们不妨换个思路,因为题目主要就是要找出两个节点的最近公共祖先,出现的所有情况如题目开头分析。所以我们可以使用一个哈希表,先存储所有的节点的父节点。然后利用题目给出的两个节点o1,o2,先取o1,遍历找出其的所有父节点(即父节点的节点都找出来),并记录起来。接着我们取o2,遍历找出其父节点,如果在遍历的过程中,发现其父节点已经访问过了,那么此时这个访问过的节点必定就是两者的最近的公共祖先了。
图片说明

代码:

    Map<Integer, TreeNode> parent = new HashMap<Integer, TreeNode>();
    Set<Integer> visited = new HashSet<Integer>();

    public int lowestCommonAncestor (TreeNode root, int o1, int o2) {
        // 先调用dfs方法
        dfs(root);
        // 创建两个节点,值为o1,o2
        TreeNode node1 = new TreeNode(o1);
        TreeNode node2 = new TreeNode(o2);
        // 对值为o1的这个节点,向上遍历找出其所有父节点(祖先节点)
        while (node1 != null) {
            visited.add(node1.val);
            // 向上
            node1 = parent.get(node1.val);
        }
        // 向上遍历值为o2的节点
        while (node2 != null) {
            // 如果已经访问过了,证明这个节点就是两个节点的最近公共祖先
            if (visited.contains(node2.val)) {
                return node2.val;
            }
            // 向上
            node2 = parent.get(node2.val);
        }
        return root.val;

    }

    // dfs先将整棵树中的节点与其父节点的信息记录起来
    public void dfs(TreeNode root) {
        // 遍历最子树
        if (root.left != null) {
            parent.put(root.left.val, root);
            dfs(root.left);
        }
        // 遍历右子树
        if (root.right != null) {
            parent.put(root.right.val, root);
            dfs(root.right);
        }
    }

复杂度分析:
时间复杂度:。n为二叉树的结点数,需要遍历n次。
空间复杂度:。当二叉树退化成链表的时候,此时递归深度为n。

CS-Review 文章被收录于专栏

本专栏记录本人维护的仓库( cs-review.cn )分类刷题解法~

全部评论

相关推荐

点赞 收藏 评论
分享
牛客网
牛客企业服务