LeetCode 1650. 二叉樹的最近公共祖先 III(哈希)

Michael阿明 2021-08-15 22:28:35 阅读数:402

本文一共[544]字,预计阅读时长:1分钟~
leetcode 二叉 最近 公共 祖先

文章目錄

1. 題目

給定一棵二叉樹中的兩個節點 p 和 q,返回它們的最近公共祖先節點(LCA)。

每個節點都包含其父節點的引用(指針)。Node 的定義如下:

class Node {

public int val;
public Node left;
public Node right;
public Node parent;
}

根據維基百科中對最近公共祖先節點的定義:“兩個節點 p 和 q 在二叉樹 T 中的最近公共祖先節點是後代節點中既包括 p 又包括 q 的最深節點(我們允許一個節點為自身的一個後代節點)”。

一個節點 x 的後代節點是節點 x 到某一葉節點間的路徑中的節點 y。

示例 1:
在這裏插入圖片描述

輸入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
輸出: 3
解釋: 節點 51 的最近公共祖先是 3

示例 2:
在這裏插入圖片描述

輸入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
輸出: 5
解釋: 節點 54 的最近公共祖先是 5,根據定義,一個節點可以是自身的最近公共祖先。
示例 3:
輸入: root = [1,2], p = 1, q = 2
輸出: 1
提示:
樹中節點個數的範圍是 [2, 10^5]-109 <= Node.val <= 109
所有的 Node.val 都是互不相同的。
p != q
p 和 q 存在於樹中。

來源:力扣(LeetCode)
鏈接:https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree-iii
著作權歸領扣網絡所有。商業轉載請聯系官方授權,非商業轉載請注明出處。

2. 解題

  • 往上找父親,並插入哈希,另一個節點也往上找,直到父親在哈希中出現
/* // Definition for a Node. class Node { public: int val; Node* left; Node* right; Node* parent; }; */
class Solution {

public:
Node* lowestCommonAncestor(Node* p, Node * q) {

unordered_set<Node*> s;
while(p)
{

s.insert(p);
p = p->parent;
}
while(q)
{

if(s.find(q) != s.end())
return q;
q = q->parent;
}
return NULL;
}
};

16 ms 11.3 MB C++

不用哈希,就是等效為鏈錶相交,求相交節點問題。


我的CSDN博客地址 https://michael.blog.csdn.net/

長按或掃碼關注我的公眾號(Michael阿明),一起加油、一起學習進步!
Michael阿明

版权声明:本文为[Michael阿明]所创,转载请带上原文链接,感谢。 https://gsmany.com/2021/08/20210815222753182Z.html