劍指 Offer 68 - II. 二叉樹的最近公共祖先

題目介紹

描述：

給定一個(gè)二叉樹, 找到該樹中兩個(gè)指定節(jié)點(diǎn)的最近公共祖先系吭。

百度百科中最近公共祖先的定義為：“對(duì)于有根樹 T 的兩個(gè)結(jié)點(diǎn) p笑窜、q璧函，最近公共祖先表示為一個(gè)結(jié)點(diǎn) x收苏，滿足 x 是 p君躺、q 的祖先且 x 的深度盡可能大（一個(gè)節(jié)點(diǎn)也可以是它自己的祖先）夸赫】美铮”

例如垮兑，給定如下二叉樹: root = [3,5,1,6,2,0,8,null,null,7,4]

示例 1:

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

輸入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
輸出: 5
解釋: 節(jié)點(diǎn) 5 和節(jié)點(diǎn) 4 的最近公共祖先是節(jié)點(diǎn) 5川队。因?yàn)楦鶕?jù)定義最近公共祖先節(jié)點(diǎn)可以為節(jié)點(diǎn)本身。

解題思路：

遞歸算法的關(guān)鍵是要明確函數(shù)的「定義」是什么睬澡，然后相信這個(gè)定義固额，利用這個(gè)定義推導(dǎo)最終結(jié)果。

寫樹相關(guān)的算法煞聪，簡單說就是斗躏，先搞清楚當(dāng)前 root 節(jié)點(diǎn)該做什么，然后根據(jù)函數(shù)定義遞歸調(diào)用子節(jié)點(diǎn)昔脯，遞歸調(diào)用會(huì)讓孩子節(jié)點(diǎn)做相同的事情啄糙。

二叉樹題目的一個(gè)難點(diǎn)在于如何通過題目的要求思考出每一個(gè)節(jié)點(diǎn)需要做什么

二叉樹解題策略

一遞歸二隊(duì)列 + 迭代（層次遍歷）三棧 + 迭代（非遞歸遍歷）四其它

三種基本的遍歷方式，都可以用遞歸來實(shí)現(xiàn)栅干。寫遞歸算法的時(shí)候迈套，需要注意遞歸退出條件以及遞歸操作的表達(dá)。

本題和之前某題不一樣的地方是碱鳞，本題是二叉樹桑李，不是搜索二叉樹。

自己的解法實(shí)現(xiàn)

def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:
        if not root or root == p or root == q: return root
        left = self.lowestCommonAncestor(root.left, p, q)
        right = self.lowestCommonAncestor(root.right, p, q)
        if left and right: return root
        return left or right

網(wǎng)上比較優(yōu)秀的解法

解法一

解題思路：祖先的定義：若節(jié)點(diǎn) p 在節(jié)點(diǎn) root 的左（右）子樹中窿给，或 p=root 贵白，則稱 root 是 p 的祖先。

最近公共祖先的定義：設(shè)節(jié)點(diǎn) root 為節(jié)點(diǎn) p,q 的某公共祖先崩泡，若其左子節(jié)點(diǎn) root.left 和右子節(jié)點(diǎn) root.right 都不是 p,q 的公共祖先禁荒，則稱 root 是 “最近的公共祖先” 。

根據(jù)以上定義角撞，若 root 是 p,q 的最近公共祖先呛伴，則只可能為以下情況之一：

p 和 q 在 root 的子樹中勃痴，且分列 root 的異側(cè)（即分別在左、右子樹中）热康； p=root 沛申，且 qq 在 root 的左或右子樹中； q=root 姐军，且 p 在 root 的左或右子樹中铁材；

考慮通過遞歸對(duì)二叉樹進(jìn)行后序遍歷，當(dāng)遇到節(jié)點(diǎn) p 或 q 時(shí)返回奕锌。從底至頂回溯著觉，當(dāng)節(jié)點(diǎn) p,q 在節(jié)點(diǎn) root 的異側(cè)時(shí)，節(jié)點(diǎn) root 即為最近公共祖先惊暴，則向上返回 root 饼丘。

def lowestCommonAncestor(self, root, p, q):
        if not root or root == p or root == q: return root
        left = self.lowestCommonAncestor(root.left, p, q)
        right = self.lowestCommonAncestor(root.right, p, q)
        if not left: return right
        if not right: return left
        return root

解法二

由于lowestCommonAncestor(root, p, q)的功能是找出以root為根節(jié)點(diǎn)的兩個(gè)節(jié)點(diǎn)p和q的最近公共祖先。我們考慮：

如果p和q分別是root的左右節(jié)點(diǎn)辽话，那么root就是我們要找的最近公共祖先
如果root是None葬毫，說明我們?cè)谶@條尋址線路沒有找到，我們返回None表示沒找到我們繼續(xù)在左右子樹執(zhí)行相同的邏輯屡穗。
如果左子樹沒找到，說明在右子樹忽肛，我們返回lowestCommonAncestor(root.right, p , q)
如果右子樹沒找到村砂，說明在左子樹，我們返回lowestCommonAncestor(root.left, p , q)
如果左子樹和右子樹分別找到一個(gè)屹逛，我們返回root

def lowestCommonAncestor2(self, root, p, q):
        if not root or root == p or root == q: return root
        left = self.lowestCommonAncestor(root.left, p, q)
        right = self.lowestCommonAncestor(root.right, p, q)
        return root if left and right else left or right

解法三

1.將每個(gè)節(jié)點(diǎn)標(biāo)記础废，記錄在字典（哈希表）里，方式為：從根節(jié)點(diǎn)開始罕模，向左為0评腺，向右為1，如示例中節(jié)點(diǎn)7標(biāo)記為“010”淑掌，節(jié)點(diǎn)4標(biāo)記為“011” 2.由兩個(gè)節(jié)點(diǎn)的標(biāo)記從頭開始的公共部分得到祖先的標(biāo)記蒿讥，如7和4的祖先標(biāo)記為“01” 3.由祖先的標(biāo)記得到祖先節(jié)點(diǎn)2

def lowestCommonAncestor3(self, root, p, q):
        stack = [root]
        _dic = {root: ""}
        while stack:
            tmp = []
            for e in stack:
                if e.left:
                    _dic[e.left] = _dic[e] + "0"
                    tmp.append(e.left)
                if e.right:
                    _dic[e.right] = _dic[e] + "1"
                    tmp.append(e.right)
            stack = tmp
        # 標(biāo)記完成，接下來根據(jù)標(biāo)記找到pq的最近公共祖先的標(biāo)記
        p_tag = _dic[p]
        q_tag = _dic[q]
        num = 0
        res_tag = ""
        while num < len(p_tag) and num < len(q_tag):
            if p_tag[num] != q_tag[num]:
                continue
            else:
                res_tag += p_tag[num]
                num += 1
        for k, v in _dic.items():
            if v == res_tag:
                return k