溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務(wù)條款》
您好，登錄后才能下訂單哦！
這篇文章將為大家詳細(xì)講解有關(guān)python二叉樹的最近公共祖先如何理解，文章內(nèi)容質(zhì)量較高，因此小編分享給大家做個參考，希望大家閱讀完這篇文章后對相關(guān)知識有一定的了解。
給定一個二叉樹, 找到該樹中兩個指定節(jié)點的最近公共祖先。
百度百科中最近公共祖先的定義為：“對于有根樹 T 的兩個結(jié)點 p、q，最近公共祖先表示為一個結(jié)點 x，滿足 x 是 p、q 的祖先且 x 的深度盡可能大（一個節(jié)點也可以是它自己的祖先）。”
例如，給定如下二叉樹: 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é)點 5 和節(jié)點 1 的最近公共祖先是節(jié)點 3。
示例 2:
輸入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
答案：
1public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
2 if (root == null || root == p || root == q)
3 return root;
4 TreeNode left = lowestCommonAncestor(root.left, p, q);
5 TreeNode right = lowestCommonAncestor(root.right, p, q);
6 return left == null ? right : right == null ? left : root;
7}
解析：
通過遞歸的方式，分別從他的左右兩個子節(jié)點往下找，如果都不為空，說明他們最近的公共祖先節(jié)點肯定是當(dāng)前root節(jié)點，如果有一個為空，說明他們最近的公共祖先節(jié)點在另一個在子節(jié)點上。這種解法和DFS很像，先從最左端的葉子節(jié)點開始找起，然后再網(wǎng)上回溯，下面再來看一種解法
1public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
2 Map<TreeNode, TreeNode> parent = new HashMap<>();
3 Deque<TreeNode> stack = new ArrayDeque<>();
4 parent.put(root, null);
5 stack.push(root);
6 while (!parent.containsKey(p) || !parent.containsKey(q)) {
7 TreeNode node = stack.pop();
8 if (node.right != null) {
9 parent.put(node.right, node);
10 stack.push(node.right);
11 }
12 if (node.left != null) {
13 parent.put(node.left, node);
14 stack.push(node.left);
15 }
16 }
17 Set<TreeNode> ancestors = new HashSet<>();
18 while (p != null) {
19 ancestors.add(p);
20 p = parent.get(p);
21 }
22 while (!ancestors.contains(q))
23 q = parent.get(q);
24 return q;
25}
Map中key記錄的是當(dāng)前節(jié)點，value記錄的是當(dāng)前節(jié)點的父節(jié)點，第一個while循環(huán)使用的是DFS，直到找到p和q節(jié)點為止，第二個while循環(huán)會把p節(jié)點以及他的的父節(jié)點，以及父節(jié)點的父節(jié)點……都加入到ancestors集合中，第3個while循環(huán)不斷的取出q節(jié)點和他的父節(jié)點以及父節(jié)點的父節(jié)點……直到在ancestors中能找到為止，找到的那個正好即是p的祖先節(jié)點也同時是q的祖先節(jié)點，同時也是最近的。
關(guān)于python二叉樹的最近公共祖先如何理解就分享到這里了，希望以上內(nèi)容可以對大家有一定的幫助，可以學(xué)到更多知識。如果覺得文章不錯，可以把它分享出去讓更多的人看到。
免責(zé)聲明：本站發(fā)布的內(nèi)容（圖片、視頻和文字）以原創(chuàng)、轉(zhuǎn)載和分享為主，文章觀點不代表本網(wǎng)站立場，如果涉及侵權(quán)請聯(lián)系站長郵箱：is@yisu.com進(jìn)行舉報，并提供相關(guān)證據(jù)，一經(jīng)查實，將立刻刪除涉嫌侵權(quán)內(nèi)容。
億速云公眾號
手機網(wǎng)站二維碼