給定一個(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)也可以是它自己的祖先）?！?/p>

?

示例 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)本身。

示例 3：

輸入：root = [1,2], p = 1, q = 2輸出：1

使用遞歸算法，自頂向下的遍歷根節(jié)點(diǎn)的左右孩子，如果找到一個(gè)節(jié)點(diǎn)就直接return；