Java怎么找二叉樹的最近公共祖先

本篇內(nèi)容主要講解“Java怎么找二叉樹的最近公共祖先”，感興趣的朋友不妨來看看。本文介紹的方法操作簡單快捷，實用性強。下面就讓小編來帶大家學(xué)習(xí)“Java怎么找二叉樹的最近公共祖先”吧!

思路一：先假設(shè)這棵樹是二叉搜索樹

首先我們補充說明一下什么是二叉搜索樹：

在二叉搜索樹中，對于每一個節(jié)點來說，他的左子樹中的值都比他小，右子樹的中的值都比他大。所以二叉搜索樹的中序遍歷是一組有序的數(shù)據(jù)。

對于上述這棵樹，假設(shè)要求 p q 的最近公共祖先。

那么它有以下情況：

對于普通的二叉樹來說，也無非就這幾種情況：pq都在左，pq都在右，pq一左一右，pq有一個是根節(jié)點。

所以分別遞歸的去左子樹和右子樹中找 p q 節(jié)點的公共祖先，找到了則返回該節(jié)點，沒有找到則返回空。

根據(jù)上述思路，我們很容易寫出代碼

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

    // p 為當(dāng)前樹的根節(jié)點
    if(p == root) return p;
    // q 為當(dāng)前樹的根節(jié)點
    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;
}

思路二：假設(shè)該樹是用孩子雙親表示法

每個節(jié)點會保存它父親節(jié)點的地址，可以層層網(wǎng)上找，直到找到兩鏈表的第一個交點，該交點就是他們的公共祖先。

而對于普通的二叉樹來說，只能層層往下找，不能往上，所以要保留兩節(jié)點的路徑，直到兩路徑的最后一個相同節(jié)點。這里我們用棧來保留兩個節(jié)點的路徑。

先彈出元素多的棧中的元素，然后兩個棧再一起彈出，直到要彈出的節(jié)點相等，就是其最近公共祖先。

那么這里最大的難點就是存儲路徑。

這里用棧來存儲路徑，當(dāng)遍歷到一個節(jié)點時，將該節(jié)點放入棧中，再遞歸該節(jié)點的左樹和右樹找，如果找到了則保留路徑，沒找到則彈出。

假設(shè)找下圖的p:

先將根節(jié)點放入棧，遞歸root節(jié)點的左子樹找，找不到則彈出，在右子樹中找。

當(dāng) root 走到 6 的時候，發(fā)現(xiàn)該節(jié)點的左右均為空，說明在該子樹中沒找到目標(biāo)節(jié)點，彈出 6 ，在 5 的右子樹中繼續(xù)找。

同理在 5 的右子樹中也找不到，會彈出直到去 3 的右子樹找，來到 1 ，找到。

// 用于找節(jié)點的路徑
public boolean getPath(TreeNode root, TreeNode node, Stack<TreeNode> stack) {
    if(root == null || node == null) {
        return false;
    }
    // 將當(dāng)前節(jié)點放入棧中
    stack.push(root);
    
    if(root.val == node.val) {
        return true;// 找到了
    }
    // 當(dāng)前節(jié)點沒找到，去左子樹找
    boolean flag = getPath(root.left,node,stack);
    // 左子樹中找到了，直接返回
    if(flag) {
        return true;
    }
    // 左子樹沒找到，去右子樹找
    flag = getPath(root.right,node,stack);
    // 右子樹中找到了，直接返回
    if(flag) {
        return true;
    }
    
    // 左右子樹都沒找到，彈出節(jié)點
    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;
        // 彈出元素直至兩棧中元素個數(shù)相等
        while(size > 0) {
            stackp.pop();
            size--;
        }
    }else {
        int size = sizeq - sizep;
        // 彈出元素直至兩棧中元素個數(shù)相等
        while(size > 0) {
            stackq.pop();
            size--;
        }
    }

    // 一起彈出，直到找到第一個相同的元素
    while(!stackp.isEmpty() && !stackq.isEmpty()) {
        if(stackp.peek() == stackq.peek()) {
        	// 找到了，就返回該節(jié)點
            return stackq.pop();
        }else {
            stackp.pop();
            stackq.pop();
        }
    }
    // 沒找到，返回 null
    return null;
}

到此，相信大家對“Java怎么找二叉樹的最近公共祖先”有了更深的了解，不妨來實際操作一番吧！這里是億速云網(wǎng)站，更多相關(guān)內(nèi)容可以進(jìn)入相關(guān)頻道進(jìn)行查詢，關(guān)注我們，繼續(xù)學(xué)習(xí)！