LeetCode（235 & 236）：二叉樹的最近公共祖先 Lowest Common Ancestor of a Binary Tree（Java）

2019.8.1 #程式員筆試必備# LeetCode 從零單刷個人筆記整理（持續更新）

二叉樹的公共祖先是一個經典的問題，在不同限制下有不同的解法：

1.如果該樹是二叉搜尋樹

那麼從根節點開始通路，若root值比p和q均小，則根節點移向右子節點；反之若root值比p和q均大，則根節點移向左子節點。第一個周遊到的位于兩子樹結點值之間的結點即為最近公共祖先。

2.如果該樹結點包含指向父節點的指針

問題可以轉換為求兩個連結清單的第一個公共結點。如果不包含指向父節點的指針，我們可以通過DFS記錄從根節點到p和q的路徑，進而轉換為求兩個路徑的第一個公共結點。

3.如果該樹是一棵普通的二叉樹

可用後序周遊标記法。若pq分别位于左右子樹，則目前根節點是最近公共祖先，若pq在同一子樹，則深度較小的結點是最近公共祖先。

1.後序周遊二叉樹，若子樹中通路到p或q，則将p或q傳回，否則傳回null，進而進行标記。

2.當左右子樹均沒有通路到p或q時，直接傳回null

3.若左子樹或右子樹僅有一棵包含p或q，則傳回該子節點。若左右子樹分别包含p和q，則傳回目前結點root。由于root的祖先已經無法在不含root的另一子樹上通路到p或q，是以函數遞歸結束仍然傳回該結點root。

傳送門：二叉搜尋樹的最近公共祖先

傳送門：二叉樹的最近公共祖先

Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.

the definition of LCA: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”

給定一個二叉樹, 找到該樹中兩個指定節點的最近公共祖先。

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

示例 1:
輸入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
輸出: 3
解釋: 節點 5 和節點 1 的最近公共祖先是節點 3。

示例 2:
輸入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
輸出: 5
解釋: 節點 5 和節點 4 的最近公共祖先是節點 5。因為根據定義最近公共祖先節點可以為節點本身。
 

說明:
所有節點的值都是唯一的。
p、q 為不同節點且均存在于給定的二叉樹中。
           

/**
 * Given a binary search tree (BST), find the lowest common ancestor (LCA) of two given nodes in the BST.
 * the definition of LCA:
 * “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”
 * 給定一個二叉搜尋樹, 找到該樹中兩個指定節點的最近公共祖先。
 * 最近公共祖先的定義為：“對于有根樹 T 的兩個結點 p、q，最近公共祖先表示為一個結點 x，滿足 x 是 p、q 的祖先且 x 的深度盡可能大（一個節點也可以是它自己的祖先）。”
 * 更新版：給定的是二叉樹而非搜尋樹
 */

public class LowestCommonAncestor0fABinarySearchTree {
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

    //求二叉搜尋樹的最近公共祖先
    //從根節點開始通路，若root值比p和q均小，則根節點移向右子節點；反之若root值比p和q均大，則根節點移向左子節點
    //第一個周遊到的位于兩子樹結點值之間的結點即為最近公共祖先
    public TreeNode lowestCommonAncestor1(TreeNode root, TreeNode p, TreeNode q) {
        while(root != null){
            if(root.val < p.val && root.val < q.val)
                root = root.right;
            else if(root.val > p.val && root.val > q.val)
                root = root.left;
            else
                break;
        }
        return root;
    }

    //更新版：求二叉樹的最近公共祖先
    //若二叉樹結點有指向父結點的指針，或創立數組建立root到pq的路徑，問題可以轉換為求兩個連結清單的第一個公共結點
    //若二叉樹結點沒有指向父節點的指針，可用後序周遊标記法。
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        //後序周遊二叉樹，若子樹中通路到p或q，則将p或q傳回，否則傳回null，進而進行标記
        if(root == null || root == p || root == q)
            return root;

        //當左右子樹均沒有通路到p或q時，直接傳回null
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        if(left == null && right == null)
            return null;

        //若左子樹或右子樹僅有一棵包含p或q，則傳回該子節點。
        //若左右子樹分别包含p和q，則傳回目前結點root。
        //由于root的祖先已經無法在不含root的另一子樹上通路到p或q，是以函數遞歸結束仍然傳回該結點root
        return left != null && right != null ? root : (left != null ? left : right);
    }

}


           

#Coding一小時，Copying一秒鐘。留個言點個贊呗，謝謝你#