題目描述

給定一個(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)本身。

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

//遞歸 func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {if root == nil {return nil}if root.Val == p.Val || root.Val == q.Val {return root}//查左子樹，返回為NIL表示找不到left := lowestCommonAncestor(root.Left, p, q)//查右子樹，返回為NIL表示找不到right := lowestCommonAncestor(root.Right, p, q)if left != nil && right != nil {return root}if left == nil {return right}return left }//存儲(chǔ)父節(jié)點(diǎn) func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {//父節(jié)點(diǎn)parent := map[int]*TreeNode{}visited := map[int]bool{}var dfs func(*TreeNode)dfs = func(r *TreeNode) {if r == nil {return}if r.Left != nil {//保存父節(jié)點(diǎn)parent[r.Left.Val] = rdfs(r.Left)}if r.Right != nil {//保存父節(jié)點(diǎn) parent[r.Right.Val] = rdfs(r.Right)}}//先遞歸一直遞歸到葉子節(jié)點(diǎn)，在執(zhí)行后面的代碼//從葉子節(jié)點(diǎn)往上記錄訪問路徑dfs(root)for p != nil {visited[p.Val] = truep = parent[p.Val]}for q != nil {if visited[q.Val] {return q}q = parent[q.Val]}return nil }

鏈接：https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree/solution/er-cha-shu-de-zui-jin-gong-gong-zu-xian-by-leetc-2/

總結(jié)

以上是生活随笔為你收集整理的二叉树的公众祖先的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。