LeetCode-Go 題解236. 二叉樹最近公共祖先Lowest Common Ancestor of a Binary Tree的遞歸解法【免費下載鏈接】LeetCode-Go? Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 題解項目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go本文基于 LeetCode-Go 倉庫中 0236.Lowest-Common-Ancestor-of-a-Binary-Tree 一題的官方題解與 Go 實現(xiàn)展開完整講解二叉樹最近公共祖先LCA的遞歸求解思路、代碼細(xì)節(jié)、復(fù)雜度分析以及倉庫內(nèi)配套的測試驗證方法。讀完本文你將掌握任意二叉樹場景下 LCA 問題的標(biāo)準(zhǔn)遞歸解法并能直接復(fù)用倉庫的測試框架驗證自己的實現(xiàn)。題目背景與 LCA 定義題目要求給定一棵二叉樹找到樹中兩個指定節(jié)點 p 和 q 的最近公共祖先Lowest Common AncestorLCA。根據(jù)維基百科對 LCA 的定義在有根樹 T 中p 與 q 的最近公共祖先是 T 中同時以 p 和 q 為后代的最低節(jié)點其中允許一個節(jié)點是其自身的后代。用中文表述就是對于有根樹 T 的兩個節(jié)點 p、q最近公共祖先表示為一個節(jié)點 x滿足 x 是 p、q 的祖先且 x 的深度盡可能大。題目給出的示例二叉樹為層序數(shù)組root [3,5,1,6,2,0,8,null,null,7,4]其結(jié)構(gòu)如下3 / \ 5 1 / \ / \ 6 2 0 8 / \ 7 4兩個官方示例Example 1p 5, q 1輸出3。節(jié)點 5 和節(jié)點 1 分別位于根節(jié)點 3 的左右子樹它們的最近公共祖先是根節(jié)點 3。Example 2p 5, q 4輸出5。節(jié)點 4 是節(jié)點 5 的后代根據(jù)節(jié)點可以是其自身后代的 LCA 定義節(jié)點 5 本身即是 p、q 的最近公共祖先。題目附帶兩條重要約束樹中所有節(jié)點的值互不相同p 和 q 是不同的節(jié)點且兩個值都一定存在于二叉樹中。這兩條約束直接保證了遞歸解法中通過指針相等而非值相等判斷命中節(jié)點的正確性。遞歸解法自底向上尋找分叉點原題解指出這是一道非常經(jīng)典的題目核心是考察遞歸。遞歸的思路可以概括為自底向上返回命中結(jié)果左右都命中時當(dāng)前節(jié)點即為 LCA。對于當(dāng)前節(jié)點 root遞歸函數(shù)lowestCommonAncestor236(root, p, q)的語義是返回以 root 為根的子樹中p 與 q 的最近公共祖先若該子樹中只包含 p 或 q 之一則返回該節(jié)點若二者都不在子樹中則返回 nil。具體地每層遞歸需要回答三個問題當(dāng)前節(jié)點是否命中若root nil子樹為空或root p、root q當(dāng)前節(jié)點就是目標(biāo)節(jié)點直接返回 root。這里root q || root p的判斷正是節(jié)點可以是其自身后代的體現(xiàn)——一旦在某一側(cè)子樹中先找到 p 或 q就無需繼續(xù)向下遞歸。左右子樹分別返回什么分別對左子樹和右子樹遞歸調(diào)用得到left與right。根據(jù)兩側(cè)結(jié)果匯總left ! nil right ! nilp 和 q 分別位于當(dāng)前節(jié)點的左右兩側(cè)子樹當(dāng)前節(jié)點就是最近公共祖先返回 root只有l(wèi)eft ! nilp、q 都在左子樹一側(cè)或其一就是左子樹返回的那個節(jié)點最近公共祖先在左子樹返回 left其余情況返回 right可能右子樹有結(jié)果也可能兩側(cè)都為空返回 nil。這一判斷邏輯恰好對應(yīng)了 LCA 的本質(zhì)最近公共祖先是 p、q 在樹中分道揚鑣的那個節(jié)點。若兩者同側(cè)則繼續(xù)深入同側(cè)子樹若兩者分居兩側(cè)則當(dāng)前節(jié)點必然是最深的同時包含二者的祖先。倉庫中的完整 Go 實現(xiàn)倉庫中本題的完整實現(xiàn)位于 236. Lowest Common Ancestor of a Binary Tree.gopackage leetcode import ( github.com/halfrost/LeetCode-Go/structures ) // TreeNode define type TreeNode structures.TreeNode /** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */ func lowestCommonAncestor236(root, p, q *TreeNode) *TreeNode { if root nil || root q || root p { return root } left : lowestCommonAncestor236(root.Left, p, q) right : lowestCommonAncestor236(root.Right, p, q) if left ! nil { if right ! nil { return root } return left } return right }實現(xiàn)只有十余行但信息密度很高逐點拆解如下類型別名復(fù)用type TreeNode structures.TreeNode把倉庫公共數(shù)據(jù)結(jié)構(gòu)包中的 TreeNode 直接復(fù)用到本題避免了每個題解目錄重復(fù)定義樹節(jié)點。TreeNode 的真實定義在 structures/TreeNode.goVal int、Left *TreeNode、Right *TreeNode。終止條件root nil || root q || root p一行同時處理了子樹為空與命中目標(biāo)兩類終止情形。后序遍歷形態(tài)先遞歸左右子樹再根據(jù)結(jié)果決定返回值本質(zhì)上是后序bottom-up遍歷保證每個節(jié)點只訪問一次。空節(jié)點安全當(dāng) p、q 不在當(dāng)前子樹時遞歸返回 nil 逐層向上傳遞最終整體返回 nil本題目約束 p、q 必在樹中正常情況下不會走到 nil 結(jié)果但代碼對這種情況依然安全。復(fù)雜度分析時間復(fù)雜度O(n)n 為二叉樹節(jié)點數(shù)。最壞情況下需要遍歷整棵樹例如 p、q 分別位于最深層的兩棵子樹每個節(jié)點恰好被訪問一次?？臻g復(fù)雜度O(h)h 為樹的高度即遞歸調(diào)用棧的深度。最壞情況下樹退化為鏈表時 h n空間復(fù)雜度退化為 O(n)平衡二叉樹場景下為 O(log n)。用示例手工推演一遍遞歸過程以 Example 1p 5, q 1為例跟蹤核心路徑從 root 3 進(jìn)入3 不是 nil、也不是 p 或 q于是遞歸左子樹和右子樹左子樹 root 5命中root p返回節(jié)點 5右子樹 root 1命中root q返回節(jié)點 1回到 root 3 這一層left節(jié)點 5與right節(jié)點 1均非 nil返回 root 3。再以 Example 2p 5, q 4為例遞歸到 root 5 時命中 p直接返回節(jié)點 5 而不再深入其子樹因此根節(jié)點 3 一側(cè)只有 left 非 nil、right 為 nil最終返回 left 即節(jié)點 5正確體現(xiàn)了節(jié)點可以是其自身后代的語義。配套測試倉庫如何驗證本題倉庫為本題編寫了完整的單元測試見 236. Lowest Common Ancestor of a Binary Tree_test.go。測試覆蓋了 5 組用例層序輸入樹pq期望輸出[]空樹--nil[3,5,1,6,2,0,8,null,null,7,4]513[3,5,1,6,2,0,8,null,null,7,4]545[6,2,8,0,4,7,9,null,null,3,5]286[6,2,8,0,4,7,9,null,null,3,5]242其中第 1 組是空樹邊界期望返回 nil第 2、4 組驗證 p、q 分居兩側(cè)的常規(guī)場景第 3、5 組驗證 p 是 q 的祖先或反之時返回祖先節(jié)點自身。測試用例的構(gòu)造方式值得關(guān)注它復(fù)用了倉庫公共結(jié)構(gòu)包提供的兩個工具函數(shù)均定義于 structures/TreeNode.goInts2TreeNode把 LeetCode 風(fēng)格的層序數(shù)組用structures.NULL表示空節(jié)點按層序用隊列構(gòu)建成二叉樹。其中NULL -1 63是倉庫約定的空節(jié)點哨兵值。GetTargetNode在構(gòu)建好的樹中按值查找目標(biāo)節(jié)點返回節(jié)點指針供測試用例作為 p、q 參數(shù)傳入。測試的核心斷言是got.Val ! a.one[0]即比較返回節(jié)點的值與期望值空樹用例則斷言返回nil。若需本地運行驗證可在倉庫根目錄執(zhí)行測試go test -v ./leetcode/0236.Lowest-Common-Ancestor-of-a-Binary-Tree/倉庫根目錄的 go.mod 通過replace github.com/halfrost/LeetCode-Go/structures ./structures把 structures 包指向本地目錄因此無需額外拉取依賴即可直接運行上述測試。對比延伸0235 二叉搜索樹版本的 LCA本題0236針對的是任意二叉樹只能依靠指針相等與遞歸遍歷求解。倉庫中還有一道姊妹題 0235. Lowest Common Ancestor of a Binary Search Tree其實現(xiàn)見 235. Lowest Common Ancestor of a Binary Search Tree.go充分利用了二叉搜索樹左小右大的性質(zhì)func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode { if p nil || q nil || root nil { return nil } if p.Val root.Val q.Val root.Val { return lowestCommonAncestor(root.Left, p, q) } if p.Val root.Val q.Val root.Val { return lowestCommonAncestor(root.Right, p, q) } return root }兩版解法的本質(zhì)區(qū)別0235BST 版通過比較節(jié)點值大小決定只向一側(cè)子樹遞歸平均復(fù)雜度 O(log n)是二分思想的直接體現(xiàn)0236普通二叉樹版無法利用值序信息必須同時探測左右兩棵子樹最壞 O(n)是分治 后序匯總思想的典型應(yīng)用。值得注意的細(xì)節(jié)是0236 版用root p || root q的指針相等判斷命中因為題目保證值唯一、指針可判等而 0235 版用p.Val root.Val的值比較引導(dǎo)搜索方向兩者正好展示了 LCA 問題在兩種樹結(jié)構(gòu)下的不同解題范式?？偨Y(jié)二叉樹最近公共祖先LCA是面試與算法競賽中的高頻經(jīng)典題。從 LeetCode-Go 倉庫的本題解可以提煉出三條核心經(jīng)驗遞歸語義要清晰明確返回什么子樹內(nèi) p、q 的 LCA或命中的單個節(jié)點或 nil代碼自然水到渠成后序匯總定答案左右子樹都命中時當(dāng)前節(jié)點即答案這是最近公共祖先 p、q 分叉點這一本質(zhì)的直接實現(xiàn)邊界與自指語義root p || root q提前返回天然支持節(jié)點可以是自身后代的 LCA 定義。如需進(jìn)一步實踐可在倉庫根目錄運行g(shù)o test -v ./leetcode/0236.Lowest-Common-Ancestor-of-a-Binary-Tree/復(fù)現(xiàn)本文全部用例并結(jié)合 structures/TreeNode.go 中的樹構(gòu)建工具自行構(gòu)造更多測試場景?！久赓M下載鏈接】LeetCode-Go? Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 題解項目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go創(chuàng)作聲明：本文部分內(nèi)容由AI輔助生成（AIGC），僅供參考 LeetCode-Go 題解：236. 二叉樹最近公共祖先（Lowest Common Ancestor of a Binary Tree）的遞歸解法
LeetCode-Go 題解236. 二叉樹最近公共祖先Lowest Common Ancestor of a Binary Tree的遞歸解法【免費下載鏈接】LeetCode-Go? Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 題解項目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go本文基于 LeetCode-Go 倉庫中 0236.Lowest-Common-Ancestor-of-a-Binary-Tree 一題的官方題解與 Go 實現(xiàn)展開完整講解二叉樹最近公共祖先LCA的遞歸求解思路、代碼細(xì)節(jié)、復(fù)雜度分析以及倉庫內(nèi)配套的測試驗證方法。讀完本文你將掌握任意二叉樹場景下 LCA 問題的標(biāo)準(zhǔn)遞歸解法并能直接復(fù)用倉庫的測試框架驗證自己的實現(xiàn)。題目背景與 LCA 定義題目要求給定一棵二叉樹找到樹中兩個指定節(jié)點 p 和 q 的最近公共祖先Lowest Common AncestorLCA。根據(jù)維基百科對 LCA 的定義在有根樹 T 中p 與 q 的最近公共祖先是 T 中同時以 p 和 q 為后代的最低節(jié)點其中允許一個節(jié)點是其自身的后代。用中文表述就是對于有根樹 T 的兩個節(jié)點 p、q最近公共祖先表示為一個節(jié)點 x滿足 x 是 p、q 的祖先且 x 的深度盡可能大。題目給出的示例二叉樹為層序數(shù)組root [3,5,1,6,2,0,8,null,null,7,4]其結(jié)構(gòu)如下3 / \ 5 1 / \ / \ 6 2 0 8 / \ 7 4兩個官方示例Example 1p 5, q 1輸出3。節(jié)點 5 和節(jié)點 1 分別位于根節(jié)點 3 的左右子樹它們的最近公共祖先是根節(jié)點 3。Example 2p 5, q 4輸出5。節(jié)點 4 是節(jié)點 5 的后代根據(jù)節(jié)點可以是其自身后代的 LCA 定義節(jié)點 5 本身即是 p、q 的最近公共祖先。題目附帶兩條重要約束樹中所有節(jié)點的值互不相同p 和 q 是不同的節(jié)點且兩個值都一定存在于二叉樹中。這兩條約束直接保證了遞歸解法中通過指針相等而非值相等判斷命中節(jié)點的正確性。遞歸解法自底向上尋找分叉點原題解指出這是一道非常經(jīng)典的題目核心是考察遞歸。遞歸的思路可以概括為自底向上返回命中結(jié)果左右都命中時當(dāng)前節(jié)點即為 LCA。對于當(dāng)前節(jié)點 root遞歸函數(shù)lowestCommonAncestor236(root, p, q)的語義是返回以 root 為根的子樹中p 與 q 的最近公共祖先若該子樹中只包含 p 或 q 之一則返回該節(jié)點若二者都不在子樹中則返回 nil。具體地每層遞歸需要回答三個問題當(dāng)前節(jié)點是否命中若root nil子樹為空或root p、root q當(dāng)前節(jié)點就是目標(biāo)節(jié)點直接返回 root。這里root q || root p的判斷正是節(jié)點可以是其自身后代的體現(xiàn)——一旦在某一側(cè)子樹中先找到 p 或 q就無需繼續(xù)向下遞歸。左右子樹分別返回什么分別對左子樹和右子樹遞歸調(diào)用得到left與right。根據(jù)兩側(cè)結(jié)果匯總left ! nil right ! nilp 和 q 分別位于當(dāng)前節(jié)點的左右兩側(cè)子樹當(dāng)前節(jié)點就是最近公共祖先返回 root只有l(wèi)eft ! nilp、q 都在左子樹一側(cè)或其一就是左子樹返回的那個節(jié)點最近公共祖先在左子樹返回 left其余情況返回 right可能右子樹有結(jié)果也可能兩側(cè)都為空返回 nil。這一判斷邏輯恰好對應(yīng)了 LCA 的本質(zhì)最近公共祖先是 p、q 在樹中分道揚鑣的那個節(jié)點。若兩者同側(cè)則繼續(xù)深入同側(cè)子樹若兩者分居兩側(cè)則當(dāng)前節(jié)點必然是最深的同時包含二者的祖先。倉庫中的完整 Go 實現(xiàn)倉庫中本題的完整實現(xiàn)位于 236. Lowest Common Ancestor of a Binary Tree.gopackage leetcode import ( github.com/halfrost/LeetCode-Go/structures ) // TreeNode define type TreeNode structures.TreeNode /** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */ func lowestCommonAncestor236(root, p, q *TreeNode) *TreeNode { if root nil || root q || root p { return root } left : lowestCommonAncestor236(root.Left, p, q) right : lowestCommonAncestor236(root.Right, p, q) if left ! nil { if right ! nil { return root } return left } return right }實現(xiàn)只有十余行但信息密度很高逐點拆解如下類型別名復(fù)用type TreeNode structures.TreeNode把倉庫公共數(shù)據(jù)結(jié)構(gòu)包中的 TreeNode 直接復(fù)用到本題避免了每個題解目錄重復(fù)定義樹節(jié)點。TreeNode 的真實定義在 structures/TreeNode.goVal int、Left *TreeNode、Right *TreeNode。終止條件root nil || root q || root p一行同時處理了子樹為空與命中目標(biāo)兩類終止情形。后序遍歷形態(tài)先遞歸左右子樹再根據(jù)結(jié)果決定返回值本質(zhì)上是后序bottom-up遍歷保證每個節(jié)點只訪問一次。空節(jié)點安全當(dāng) p、q 不在當(dāng)前子樹時遞歸返回 nil 逐層向上傳遞最終整體返回 nil本題目約束 p、q 必在樹中正常情況下不會走到 nil 結(jié)果但代碼對這種情況依然安全。復(fù)雜度分析時間復(fù)雜度O(n)n 為二叉樹節(jié)點數(shù)。最壞情況下需要遍歷整棵樹例如 p、q 分別位于最深層的兩棵子樹每個節(jié)點恰好被訪問一次?？臻g復(fù)雜度O(h)h 為樹的高度即遞歸調(diào)用棧的深度。最壞情況下樹退化為鏈表時 h n空間復(fù)雜度退化為 O(n)平衡二叉樹場景下為 O(log n)。用示例手工推演一遍遞歸過程以 Example 1p 5, q 1為例跟蹤核心路徑從 root 3 進(jìn)入3 不是 nil、也不是 p 或 q于是遞歸左子樹和右子樹左子樹 root 5命中root p返回節(jié)點 5右子樹 root 1命中root q返回節(jié)點 1回到 root 3 這一層left節(jié)點 5與right節(jié)點 1均非 nil返回 root 3。再以 Example 2p 5, q 4為例遞歸到 root 5 時命中 p直接返回節(jié)點 5 而不再深入其子樹因此根節(jié)點 3 一側(cè)只有 left 非 nil、right 為 nil最終返回 left 即節(jié)點 5正確體現(xiàn)了節(jié)點可以是其自身后代的語義。配套測試倉庫如何驗證本題倉庫為本題編寫了完整的單元測試見 236. Lowest Common Ancestor of a Binary Tree_test.go。測試覆蓋了 5 組用例層序輸入樹pq期望輸出[]空樹--nil[3,5,1,6,2,0,8,null,null,7,4]513[3,5,1,6,2,0,8,null,null,7,4]545[6,2,8,0,4,7,9,null,null,3,5]286[6,2,8,0,4,7,9,null,null,3,5]242其中第 1 組是空樹邊界期望返回 nil第 2、4 組驗證 p、q 分居兩側(cè)的常規(guī)場景第 3、5 組驗證 p 是 q 的祖先或反之時返回祖先節(jié)點自身。測試用例的構(gòu)造方式值得關(guān)注它復(fù)用了倉庫公共結(jié)構(gòu)包提供的兩個工具函數(shù)均定義于 structures/TreeNode.goInts2TreeNode把 LeetCode 風(fēng)格的層序數(shù)組用structures.NULL表示空節(jié)點按層序用隊列構(gòu)建成二叉樹。其中NULL -1 63是倉庫約定的空節(jié)點哨兵值。GetTargetNode在構(gòu)建好的樹中按值查找目標(biāo)節(jié)點返回節(jié)點指針供測試用例作為 p、q 參數(shù)傳入。測試的核心斷言是got.Val ! a.one[0]即比較返回節(jié)點的值與期望值空樹用例則斷言返回nil。若需本地運行驗證可在倉庫根目錄執(zhí)行測試go test -v ./leetcode/0236.Lowest-Common-Ancestor-of-a-Binary-Tree/倉庫根目錄的 go.mod 通過replace github.com/halfrost/LeetCode-Go/structures ./structures把 structures 包指向本地目錄因此無需額外拉取依賴即可直接運行上述測試。對比延伸0235 二叉搜索樹版本的 LCA本題0236針對的是任意二叉樹只能依靠指針相等與遞歸遍歷求解。倉庫中還有一道姊妹題 0235. Lowest Common Ancestor of a Binary Search Tree其實現(xiàn)見 235. Lowest Common Ancestor of a Binary Search Tree.go充分利用了二叉搜索樹左小右大的性質(zhì)func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode { if p nil || q nil || root nil { return nil } if p.Val root.Val q.Val root.Val { return lowestCommonAncestor(root.Left, p, q) } if p.Val root.Val q.Val root.Val { return lowestCommonAncestor(root.Right, p, q) } return root }兩版解法的本質(zhì)區(qū)別0235BST 版通過比較節(jié)點值大小決定只向一側(cè)子樹遞歸平均復(fù)雜度 O(log n)是二分思想的直接體現(xiàn)0236普通二叉樹版無法利用值序信息必須同時探測左右兩棵子樹最壞 O(n)是分治 后序匯總思想的典型應(yīng)用。值得注意的細(xì)節(jié)是0236 版用root p || root q的指針相等判斷命中因為題目保證值唯一、指針可判等而 0235 版用p.Val root.Val的值比較引導(dǎo)搜索方向兩者正好展示了 LCA 問題在兩種樹結(jié)構(gòu)下的不同解題范式?？偨Y(jié)二叉樹最近公共祖先LCA是面試與算法競賽中的高頻經(jīng)典題。從 LeetCode-Go 倉庫的本題解可以提煉出三條核心經(jīng)驗遞歸語義要清晰明確返回什么子樹內(nèi) p、q 的 LCA或命中的單個節(jié)點或 nil代碼自然水到渠成后序匯總定答案左右子樹都命中時當(dāng)前節(jié)點即答案這是最近公共祖先 p、q 分叉點這一本質(zhì)的直接實現(xiàn)邊界與自指語義root p || root q提前返回天然支持節(jié)點可以是自身后代的 LCA 定義。如需進(jìn)一步實踐可在倉庫根目錄運行g(shù)o test -v ./leetcode/0236.Lowest-Common-Ancestor-of-a-Binary-Tree/復(fù)現(xiàn)本文全部用例并結(jié)合 structures/TreeNode.go 中的樹構(gòu)建工具自行構(gòu)造更多測試場景?！久赓M下載鏈接】LeetCode-Go? Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 題解項目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go創(chuàng)作聲明：本文部分內(nèi)容由AI輔助生成（AIGC），僅供參考