Bagaimana untuk mencari nenek moyang terdekat pokok binari di Jawa

Idea 1: Mula-mula andaikan pokok ini ialah pokok carian binari

Pertama sekali, mari kita tambahkan penjelasan tambahan tentang pokok carian binari:

Dalam carian binari pokok, untuk setiap Untuk nod, nilai dalam subpokok kirinya lebih kecil daripadanya, dan nilai dalam subpokok kanannya lebih besar daripadanya. Jadi traversal tertib bagi pepohon carian binari ialah set data tersusun.

Untuk pokok di atas, anggap bahawa nenek moyang biasa p q yang paling terkini diperlukan.

Kemudian ia mempunyai situasi berikut:

Untuk pokok binari biasa, tidak ada yang lebih daripada situasi ini. : pq semuanya di sebelah kiri, pq semuanya di sebelah kanan, pq ialah satu di sebelah kiri dan satu di sebelah kanan, dan satu daripada pq ialah nod akar.

Jadi secara rekursif pergi ke subpokok kiri dan subpokok kanan untuk mencari nenek moyang biasa nod p q Jika ia ditemui, nod akan dikembalikan jika ia tidak dijumpai.

Mengikut idea di atas, mudah untuk kita menulis kod

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    if(root == null) return null;

    // p 为当前树的根节点
    if(p == root) return p;
    // q 为当前树的根节点
    if(q == root) return q;
    
    // 去左子树中找
    TreeNode left = lowestCommonAncestor(root.left,p,q);
    // 去右子树中找
    TreeNode right = lowestCommonAncestor(root.right,p,q);

    // 左边右边都找到了
    if(left != null && right != null) {
        return root;
    }
    // 左边找到了，右边没找到
    if(left != null) {
        return left;
    }
    if(right != null) {
        return right;
    }
    return null;
}

Idea 2: Andaikan pokok itu menggunakan perwakilan induk anak

Setiap nod akan menyimpan alamat nod bapanya, yang boleh dicari dalam talian lapisan demi lapisan sehingga titik persilangan pertama kedua-duanya senarai terpaut ditemui, titik persimpangan mana yang menjadi nenek moyang mereka.

Untuk pokok binari biasa, anda hanya boleh mencari ke bawah lapisan demi lapisan, bukan ke atas, jadi anda perlu mengekalkan laluan kedua-dua nod sehingga yang terakhir daripada dua laluan adalah sama. Di sini kita menggunakan timbunan untuk mengekalkan laluan dua nod.

Mula-mula pop elemen dalam tindanan dengan lebih banyak elemen, dan kemudian cantumkan dua tindanan bersama-sama sehingga nod yang akan ditimbulkan adalah sama, iaitu nenek moyang terdekat mereka.

Maka kesukaran terbesar di sini ialah laluan penyimpanan.

Di sini tindanan digunakan untuk menyimpan laluan Apabila nod dilalui, nod dimasukkan ke dalam tindanan, dan kemudian pokok kiri dan pokok kanan nod dicari secara rekursif dikekalkan jika tidak dijumpai, kemudian timbul.

Andaikan anda sedang mencari p dalam rajah di bawah:

Mula-mula masukkan nod akar ke dalam timbunan, cari subpokok kiri akar secara rekursif nod, dan timbulkannya jika ia tidak dijumpai, cari dalam subpokok yang betul.

Apabila punca mencapai 6, didapati bahagian kiri dan kanan nod kosong, menunjukkan bahawa nod sasaran tidak ditemui dalam subpokok, dan 6 timbul atas, di sebelah kanan 5 Teruskan mencari dalam subpokok.

Begitu juga, ia tidak boleh ditemui dalam subpokok kanan 5. Ia akan muncul sehingga ia pergi ke subpokok kanan 3 dan menemui 1.

// 用于找节点的路径
public boolean getPath(TreeNode root, TreeNode node, Stack<TreeNode> stack) {
    if(root == null || node == null) {
        return false;
    }
    // 将当前节点放入栈中
    stack.push(root);
    
    if(root.val == node.val) {
        return true;// 找到了
    }
    // 当前节点没找到，去左子树找
    boolean flag = getPath(root.left,node,stack);
    // 左子树中找到了，直接返回
    if(flag) {
        return true;
    }
    // 左子树没找到，去右子树找
    flag = getPath(root.right,node,stack);
    // 右子树中找到了，直接返回
    if(flag) {
        return true;
    }
    
    // 左右子树都没找到，弹出节点
    stack.pop();
    return false;

}
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    if(root == null) {
        return null;
    }
    Stack<TreeNode> stackp = new Stack<>();
    Stack<TreeNode> stackq = new Stack<>();

    // 分别得到  p q 的路径
    getPath(root,p,stackp);
    getPath(root,q,stackq);

    int sizep = stackp.size();
    int sizeq = stackq.size();

    if(sizep > sizeq) {
        int size = sizep - sizeq;
        // 弹出元素直至两栈中元素个数相等
        while(size > 0) {
            stackp.pop();
            size--;
        }
    }else {
        int size = sizeq - sizep;
        // 弹出元素直至两栈中元素个数相等
        while(size > 0) {
            stackq.pop();
            size--;
        }
    }

    // 一起弹出，直到找到第一个相同的元素
    while(!stackp.isEmpty() && !stackq.isEmpty()) {
        if(stackp.peek() == stackq.peek()) {
        	// 找到了，就返回该节点
            return stackq.pop();
        }else {
            stackp.pop();
            stackq.pop();
        }
    }
    // 没找到，返回 null
    return null;
}

Atas ialah kandungan terperinci Bagaimana untuk mencari nenek moyang terdekat pokok binari di Jawa. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!