Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commitb3b35e6

Browse files
Update
1 parent5fc065c commitb3b35e6

File tree

5 files changed

+106
-1
lines changed

5 files changed

+106
-1
lines changed

‎README.md

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -86,6 +86,7 @@
8686
*[二叉树：听说递归能做的，栈也能做！](https://mp.weixin.qq.com/s/c_zCrGHIVlBjUH_hJtghCg)
8787
*[二叉树：前中后序迭代方式的写法就不能统一一下么？](https://mp.weixin.qq.com/s/WKg0Ty1_3SZkztpHubZPRg)
8888
*[二叉树：层序遍历登场！](https://mp.weixin.qq.com/s/Gb3BjakIKGNpup2jYtTzog)
89+
*[二叉树：你真的会翻转二叉树么？](https://mp.weixin.qq.com/s/6gY1MiXrnm-khAAJiIb5Bg)
8990

9091
（持续更新中....）
9192

Loading

‎problems/0102.二叉树的层序遍历.md

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -267,7 +267,7 @@ public:
267267
* 107.二叉树的层次遍历II
268268
* 199.二叉树的右视图
269269
* 637.二叉树的层平均值
270-
*589.N叉树的前序遍历
270+
*429.N叉树的前序遍历
271271
* 515.在每个树行中找最大值
272272

273273
虽然不能一口气打十个，打六个也还行。
Lines changed: 98 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,98 @@
1+
##链接
2+
https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-search-tree/
3+
4+
##思路
5+
6+
7+
遇到这个题目首先想的是要是能自底向上查找就好了，这样就可以找到公共祖先了，可惜二叉树只能自上向低。
8+
9+
那么自上相下查找的话，如何记录祖先呢？
10+
11+
做过[236. 二叉树的最近公共祖先](https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree/)题目的同学，应该知道，只要判断一个节点的左子树里有p，右子树里有q，那么当前节点就是最近公共祖先。
12+
13+
那么本题是二叉搜索树，二叉搜索树是有序的，那得好好利用一下这个特点。
14+
15+
在有序树里，如果判断一个节点的左子树里有p，右子树里有q呢？
16+
17+
其实只要从上到下遍历的时候，如果 (p->val <= cur->val && cur->val <= q->val)则说明该节点cur就是最近公共祖先了。
18+
19+
理解这一点，本题就很好解了。
20+
21+
如图所示
22+
23+
<imgsrc='../pics/235.二叉搜索树的最近公共祖先.png'width=600> </img></div>
24+
25+
在遍历二叉搜索树的时候就是寻找区间[p->val, q->val]（注意这里是左闭又闭）
26+
27+
那么如果 cur->val 大于 p->val，同时 cur->val 大于q->val，那么就应该向左遍历。（因为我们此时不知道p和q谁大，所以两个都要判断）
28+
29+
代码如下：
30+
31+
```
32+
if (cur->val > p->val && cur->val > q->val) {
33+
return traversal(cur->left, p, q);
34+
}
35+
```
36+
37+
如果 cur->val 小于 p->val，同时 cur->val 小于 q->val，那么就应该向右遍历。
38+
39+
```
40+
} else if (cur->val < p->val && cur->val < q->val) {
41+
return traversal(cur->right, p, q);
42+
}
43+
```
44+
45+
剩下的情况，我们就找到了区间使（p->val <= cur->val && cur->val <= q->val）或者是 （q->val <= cur->val && cur->val <= p->val）
46+
47+
代码如下：
48+
```
49+
else {
50+
return cur;
51+
}
52+
53+
```
54+
55+
那么整体递归代码如下:
56+
57+
##C++递归代码
58+
59+
（我这里特意把递归的过程抽出一个函数traversal，这样代码更清晰，有助于读者理解。）
60+
61+
```
62+
class Solution {
63+
private:
64+
TreeNode* traversal(TreeNode* cur, TreeNode* p, TreeNode* q) {
65+
if (cur->val > p->val && cur->val > q->val) {
66+
return traversal(cur->left, p, q);
67+
} else if (cur->val < p->val && cur->val < q->val) {
68+
return traversal(cur->right, p, q);
69+
} else return cur;
70+
}
71+
public:
72+
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
73+
74+
return traversal(root, p, q);
75+
}
76+
};
77+
```
78+
79+
80+
##C++迭代法代码
81+
82+
同时给出一个迭代的版本，思想是一样的，代码如下：
83+
84+
```
85+
class Solution {
86+
public:
87+
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
88+
while(root) {
89+
if (root->val > p->val && root->val > q->val) {
90+
root = root->left;
91+
} else if (root->val < p->val && root->val < q->val) {
92+
root = root->right;
93+
} else return root;
94+
}
95+
return NULL;
96+
}
97+
};
98+
```

‎problems/链表总结篇.md

Lines changed: 6 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,6 @@
1+
2+
*[关于链表，你该了解这些！](https://mp.weixin.qq.com/s/ntlZbEdKgnFQKZkSUAOSpQ)
3+
*[链表：听说用虚拟头节点会方便很多？](https://mp.weixin.qq.com/s/slM1CH5Ew9XzK93YOQYSjA)
4+
*[链表：一道题目考察了常见的五个操作！](https://mp.weixin.qq.com/s/Cf95Lc6brKL4g2j8YyF3Mg)
5+
*[链表：听说过两天反转链表又写不出来了？](https://mp.weixin.qq.com/s/pnvVP-0ZM7epB8y3w_Njwg)
6+
*[链表：环找到了，那入口呢？](https://mp.weixin.qq.com/s/_QVP3IkRZWx9zIpQRgajzA)

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp