【問題描述】[中等]

235/68-1 搜索二叉樹 236/68-2 二叉樹

【解答思路】

遞歸

時間復雜度：O(N) 空間復雜度：O(N)

情況 1. , 2. , 3. , 4. 的展開寫法如下。

class Solution {public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {if(root == null || root == p || root == q) return root;TreeNode left = lowestCommonAncestor(root.left, p, q);TreeNode right = lowestCommonAncestor(root.right, p, q);if(left == null && right == null) return null; // 1.if(left == null) return right; // 3.if(right == null) return left; // 4.return root; // 2. if(left != null and right != null)} }

優(yōu)化版

class Solution {public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {if(root == null || root == p || root == q) return root;TreeNode left = lowestCommonAncestor(root.left, p, q);TreeNode right = lowestCommonAncestor(root.right, p, q);if(left == null) return right;if(right == null) return left;return root;} }

注釋版

//方法二：后序遍歷，先左子樹后右子樹最后root,從底至頂回溯，代碼簡單，但是分析起來復雜;//當root==null時，說明當前路徑?jīng)]有找到p或者q//當root==p||root==q,假設先找到的是節(jié)點p://則繼續(xù)從找到的節(jié)點p開始尋找另一個節(jié)點q(迭代)，當?shù)诙€節(jié)點q也找到時,進行回溯,一開始回溯時，會一直保持單側(cè)子樹不為null的情況，但是注意這種情況，不是由于p,q均在當前單側(cè)子樹造成的，當前回溯過程的單側(cè)子樹內(nèi)只有一個q;//繼續(xù)回溯，當回溯至一個節(jié)點root時,節(jié)點 p,q在節(jié)點root的異側(cè),即雙側(cè)子樹均不為null時,節(jié)點 root即為最近公共祖先。//返回root，后續(xù)則又會變?yōu)閱蝹?cè)子樹不為null,這時才是因為p,q均在當前單側(cè)子樹造成的;public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {//root=null,返回root說明這條路徑?jīng)]有找到p或者q;root=p||root=q時說明當前找到了p或者q;if(root==null||root==p||root==q) return root;TreeNode left = lowestCommonAncestor(root.left,p,q);TreeNode right = lowestCommonAncestor(root.right,p,q);//后面是回溯過程,下面三個if語句可以交換順序，如果固定順序，則后面兩個if可以進行簡化//當root的左子樹和右子樹都沒有p或者q時，root不是p和q祖先,返回null;if(left==null&&right==null) return null;//基于第一個if，這里的if可以簡寫為if(right==null) return left;//這里root的右子樹沒有找到p或者q,left找到了p或者q,這里返回的left有兩種情況：//1.未找到最近公共節(jié)點時，即還在迭代階段，這里返回的left為找到的p(假設為p),即第一個if的return結(jié)果：//若前面沒有找到q,則從p開始繼續(xù)進行迭代,在二叉樹中剩余的節(jié)點中找到剩下的那個q; 若之前已經(jīng)找到了q，則開始返回，直到找到left!=null&&right!=null，即找到了最近公共祖宗；//2.找到最近公共節(jié)點時，即處于返回階段,不需要再進行迭代了,此時p,q在同一側(cè)子樹中,這里left為找到的最近公共節(jié)點,即下面最后一個return的結(jié)果;if(left!=null&&right==null) return left;//基于第一個if，這里的if可以簡寫為if(left==null) return right;//這里的分析和上面一個if類似;if(left==null&&right!=null) return right;return root;//即if(left!=null&&right!=null) return root;但注釋中的寫法會使得函數(shù)缺少return語句;}

【總結(jié)】

1. 二叉樹遍歷

前序遍歷 先輸出當前結(jié)點的數(shù)據(jù)，再依次遍歷輸出左結(jié)點和右結(jié)點
中序遍歷 先遍歷輸出左結(jié)點，再輸出當前結(jié)點的數(shù)據(jù)，再遍歷輸出右結(jié)點
后續(xù)遍歷 先遍歷輸出左結(jié)點，再遍歷輸出右結(jié)點，最后輸出當前結(jié)點的數(shù)據(jù)

2. 對于二叉樹的題，開始可以用遞歸的思想去思考單 代碼簡單 過程不簡單

3. 相關題目[劍指offer]面試題第[68-1]題[Leedcode][JAVA][第235題][二叉搜索樹的最近公共祖先][遞歸][BFS]

作者：Krahets
轉(zhuǎn)載鏈接：https://leetcode-cn.com/problems/er-cha-shu-de-zui-jin-gong-gong-zu-xian-lcof/solution/mian-shi-ti-68-ii-er-cha-shu-de-zui-jin-gong-gon-7/

參考鏈接：https://leetcode-cn.com/problems/er-cha-shu-de-zui-jin-gong-gong-zu-xian-lcof/solution/mian-shi-ti-68-ii-javashi-xian-jian-zhi-offersi-lu/

總結(jié)

以上是生活随笔為你收集整理的[剑指offer]面试题第[68-2]题[Leetcode][第236题][JAVA][二叉搜索树的最近公共祖先][递归]的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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