文章目錄

• 題目描述
• 思路 & 代碼

題目描述

• ac了，但是看了題解發(fā)現(xiàn)有更好的做法
  

思路 & 代碼

• 對于一個結(jié)點rootNode，p、q有這么幾種情況：

p、q分別在其左右子樹中，那么好說，rootNode就是答案

p、q都在其右子樹中（包括p or q就是rootNode)，那么就以rootNode.right開始進行新的遞歸

p、q都在其左子樹中，和2差不多

• 由此，流程：先遞歸left & right，都不為null的情況就是情況1。其中一方為null的情況就是情況2、3，在遞歸中返回最終結(jié)果。

/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode(int x) { val = x; }* }*/class Solution {public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {// 葉子結(jié)點 & 已經(jīng)找到 p or q 的情況下返回 rootif(root == null || root == p || root == q){return root;} TreeNode right = lowestCommonAncestor(root.right, p, q);TreeNode left = lowestCommonAncestor(root.left, p, q);// left == null的情況，說明兩結(jié)點都在root的右側(cè)if(left == null){return right;}// 類似上，都在左側(cè)if(right == null){return left;}// 否則說明分布在root的左右兩側(cè)，那么root就是最近公共父結(jié)點。return root;} }

• 自己想的方法：用兩條鏈表，按深度存儲p、q所有父結(jié)點
• 然后建立哈希集，存儲q的所有父結(jié)點
• 接著用q來查找哈希集中最近的父結(jié)點即可。

/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode(int x) { val = x; }* }*/// ac了，但是效率比較低，O(n * 4) & O(n * 3)，總體來說還是O(n) O(n)的。class Solution {boolean found;public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {// 提示很重要LinkedList<TreeNode> superP = new LinkedList<>();LinkedList<TreeNode> superQ = new LinkedList<>();findSuper(superP, root, p);found = false;findSuper(superQ, root, q);// 接下來用HashSet來找最近的公共子結(jié)點Set<TreeNode> hash = new HashSet();for(TreeNode temp : superP){hash.add(temp);} while(true){TreeNode temp = superQ.removeLast();if(hash.contains(temp)){return temp;}}}// 包括自己，自己也存入void findSuper(LinkedList<TreeNode> superP, TreeNode root, TreeNode target){if(root == null){return;}superP.add(root);// 找到了，結(jié)束尋找。if(root == target){found = true;return;}// 還沒找到，繼續(xù)找findSuper(superP, root.left, target);// 判斷一下左邊遞歸有沒有找到if(!found){findSuper(superP, root.right, target);}// 以當(dāng)前root開始的遞歸結(jié)束，刪掉當(dāng)前父結(jié)點if(!found){superP.removeLast();}} }

總結(jié)

以上是生活随笔為你收集整理的【LeetCode笔记】236. 二叉树的最近公共祖先（Java、二叉树、DFS）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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