算法-二叉树-最低公共祖先

2022-4-11 diaba 笔试题 

package com.jiucaiyuan.net.algrithm.tree;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/**
 * <pre>
 * 【问题】给定二叉树的两个节点node1和node2，找到他们最低公共祖先
 * 【概念】最低公共祖先：两个节点往root节点的链路，第一个相交的节点
 * 【思路】
 * </pre>
 *
 * @Author jiucaiyuan  2022/4/10 23:55
 * @mail services@jiucaiyuan.net
 */

public class LowestCommonAncestor {

    /**
     * <pre>
     * 最低公共祖先
     * 思路：从树中所有子树递归查找node1和node2，只要看到其一，就返回，左树和右树中都找到了，
     * 那么最低祖先一定是当前node，如果其中一个树找到了，另一个子树没有都找到，
     * 则一定是其中一个是另一个的祖先
     * </pre>
     * @param head
     * @param node1
     * @param node2
     * @return
     */
    public static Node lowestAncestor(Node head, Node node1, Node node2) {
        if (head == null || head == node1 || head == node2) {
            return head;
        }
        Node left = lowestAncestor(head.left, node1, node2);
        Node right = lowestAncestor(head.right, node1, node2);
        if (left != null && right != null) {
            return head;
        }
        return left != null ? left : right;
    }


    /**
     * 在head中找到node1和node2的最低公共祖先，node1和node2一定是head中的节点
     * 思路：先构建node1到head的整条链节点池，再访问node2到head节点路径，看那个再池中哪个就是
     *
     * @param head
     * @param node1
     * @param node2
     * @return
     */
    public static Node lca(Node head, Node node1, Node node2) {
        //构建整棵树的节点与父节点关系
        Map<Node, Node> fatherMap = new HashMap<>();
        fatherMap.put(head, head);
        process(head, fatherMap);

        //node1到父节点之间的节点放入set
        Set<Node> set = new HashSet<>();
        Node curr = node1;
        while (curr != fatherMap.get(curr)) {
            set.add(curr);
            curr = fatherMap.get(curr);
        }
        set.add(head);
        //再从node2开始逐个节点靠近head处理
        curr = node2;
        while (curr != fatherMap.get(curr)) {
            if (set.contains(curr)) {
                return curr;
            }
        }
        return head;
    }

    /**
     * 遍历head，把所有节点的和父节点的对应关系建立起来
     *
     * @param head
     * @param fatherMap
     */
    private static void process(Node head, Map<Node, Node> fatherMap) {
        if (head == null) {
            return;
        }
        fatherMap.put(head.left, head);
        fatherMap.put(head.right, head);
        process(head.left, fatherMap);
        process(head.right, fatherMap);
    }
}

« 算法-二叉树-序列化&反序列化 | 算法-二叉树-判断满二叉树»

发表评论：

Powered by emlog 京ICP备15045175号-1 Copyright © 2022