【問(wèn)題描述】

給定一個(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)也可以是它自己的祖先）。”例如，給定如下二叉樹(shù): root = [3,5,1,6,2,0,8,null,null,7,4]輸入: 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。

【解答思路】

1. DFS 后序遍歷

時(shí)間復(fù)雜度：O(N^2) 空間復(fù)雜度：O(N)

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)} }

2. 路徑法

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {Stack<TreeNode> stack = new Stack<>();HashMap<TreeNode, TreeNode> parent = new HashMap<>();//初始化根節(jié)點(diǎn)stack.push(root);parent.put(root, null);//將遍歷過(guò)程中每個(gè)節(jié)點(diǎn)的父節(jié)點(diǎn)保存起來(lái)while (!parent.containsKey(p) || !parent.containsKey(q)) {TreeNode cur = stack.pop();if (cur.left != null) {stack.push(cur.left);parent.put(cur.left, cur);}if (cur.right != null) {stack.push(cur.right);parent.put(cur.right, cur);}}HashSet<TreeNode> path = new HashSet<>();// 倒著還原 p 的路徑，并將每個(gè)節(jié)點(diǎn)加入到 set 中while (p != null) {path.add(p);p = parent.get(p);}// 倒著遍歷 q 的路徑，判斷是否在 p 的路徑中while (q != null) {if (path.contains(q)) {break;}q = parent.get(q);}return q; }

【總結(jié)】

1.二叉樹(shù)遍歷

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

2. 樹(shù)的問(wèn)題DFS BFS 遞歸思想 剪枝優(yōu)化

3.堆棧+HashMap（記錄父節(jié)點(diǎn)）+HashSet（記錄路徑）

轉(zhuǎn)載鏈接:https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree/solution/236-er-cha-shu-de-zui-jin-gong-gong-zu-xian-hou-xu/
轉(zhuǎn)載鏈接：https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree/solution/xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-by-5-2/

總結(jié)

以上是生活随笔為你收集整理的[Leedcode][JAVA][第236题][二叉树的公共祖先][后序遍历][BFS]的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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