題目
給定一個(gè)二叉樹(shù), 找到該樹(shù)中兩個(gè)指定節(jié)點(diǎn)的最近公共祖先圈膏。
百度百科中最近公共祖先的定義為：“對(duì)于有根樹(shù) T 的兩個(gè)結(jié)點(diǎn) p、q，最近公共祖先表示為一個(gè)結(jié)點(diǎn) x，滿足 x 是 p傅物、q 的祖先且 x 的深度盡可能大（一個(gè)節(jié)點(diǎn)也可以是它自己的祖先）×鹪ぃ”
例如董饰，給定如下二叉樹(shù): 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)本身。
說(shuō)明:
所有節(jié)點(diǎn)的值都是唯一的贮缅。
p榨咐、q 為不同節(jié)點(diǎn)且均存在于給定的二叉樹(shù)中。
來(lái)源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有谴供。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)块茁，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。
解題思路
使用遞歸的方法求解
- 如果空桂肌，或者其中一個(gè)節(jié)點(diǎn)是跟節(jié)點(diǎn)数焊，返回跟節(jié)點(diǎn)
- 在左子樹(shù)中尋找 p q
- 在右子樹(shù)中尋找 p q
- 如果左右子樹(shù)中都找到了一個(gè)點(diǎn)，那返回跟節(jié)點(diǎn)崎场， 否則返回找到節(jié)點(diǎn)的子樹(shù)佩耳。
代碼
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def lowestCommonAncestor(self, root, p, q):
"""
:type root: TreeNode
:type p: TreeNode
:type q: TreeNode
:rtype: TreeNode
"""
# if not root:
# return None
if not root or p == root or q == root:
return root
left = self.lowestCommonAncestor(root.left, p, q)
right = self.lowestCommonAncestor(root.right, p, q)
if left and right:
return root
if left:
return left
if right:
return right
