Java_[最近公共祖先]兩種題型詳解

       在求解“最近公共祖先”的問題時，會遇到兩種問題，一種是基于樹狀結構下求公共祖先、一種是一組帶有連續編号的數字在樹的結構下進行布局。

       題目一：

      将一棵無窮大滿二叉樹的結點按根結點一層一層地從左往右編号，根結點編号為1。現給定a，b為兩個結點。設計一個算法，傳回a、b最近的公共祖先的編号。注意其祖先也可能是結點本身。

https://www.nowcoder.com/practice/70e00e490b454006976c1fdf47f155d9?tpId=8&&tqId=11017&rp=1&ru=/activity/oj&qru=/ta/cracking-the-coding-interview/question-ranking

      題目二：

       給定一個二叉樹, 找到該樹中兩個指定節點的最近公共祖先。百度百科中最近公共祖先的定義為：“對于有根樹 T 的兩個節點 p、q，最近公共祖先表示為一個節點 x，滿足 x 是 p、q 的祖先且 x 的深度盡可能大（一個節點也可以是它自己的祖先）。”

https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree/

看完本章題解可以點開兩個題目的連結試試~~~

題目一解析：

        若根節點為1，那麼p和q的根節點判定可以分為兩種情況。

        1.若p == q，那麼p和q的最近公共祖先則可以表示為p和q中任意一個值，表明此時已經找到該兩個節點的最近公共祖先，此時函數調用結束。

        2.若p > q或者q > q，那麼需要每次挑出p和q中的最大值，進行取模2運算，直到回歸到第一種情況，傳回最近共祖祖先值，調用函數結束。

        Java解決函數代碼如下：

import java.util.*;

public class LCA {
    public int getLCA(int a, int b) {
        // write code here
        while(a != b) {//每次取最大值進行模2運算，直至a和b兩值相同
            if(a > b) {
                a /= 2;
            } else {
                b /= 2;
            }
        }
        return a;
    }
}           

        題目二解析：

           在每個節點的判定節點時，可分為如下情況：

           1.此時根節點為null或者左節點或者右節點為null時，傳回null，表明兩節點無最近公共祖先，結束此次函數調用。

           2.此時左節點為null且右節點不為null時，傳回右節點的值。

           3.此時右節點為null且左節點不為null時，傳回左節點的值。

           4.此時左節點和右節點都不為null時，傳回左右節點的根節點值。

       每次遞歸查詢樹狀結構的左子樹和右子樹，通過前面的4種條件判定目前最近公共祖先的值，并傳回結果。

            Java解決問題代碼如下：

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null) return null;
        if(p == null || q == null) return null;
        if(root == p || root == q) return root;
        TreeNode leftNode = lowestCommonAncestor(root.left,p,q);
        TreeNode rightNode = lowestCommonAncestor(root.right,p,q);
        if(leftNode != null && rightNode == null) return leftNode;
        if(leftNode == null && rightNode != null) return rightNode;
        if(leftNode != null && rightNode != null) return root;
        return null;
    }
}