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

Commit262a6e5

Browse files
author
liningrui
committed
add new solutions
1 parent3e45eec commit262a6e5

File tree

28 files changed

+965
-9
lines changed

28 files changed

+965
-9
lines changed

‎script/[109]有序链表转换二叉搜索树.py

Lines changed: 20 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -29,7 +29,7 @@
2929
# head 中的节点数在[0, 2 * 10⁴] 范围内
3030
# -10⁵ <= Node.val <= 10⁵
3131
#
32-
# Related Topics 树 二叉搜索树 链表 分治 二叉树 👍729 👎 0
32+
# Related Topics 树 二叉搜索树 链表 分治 二叉树 👍730 👎 0
3333

3434

3535
# leetcode submit region begin(Prohibit modification and deletion)
@@ -46,4 +46,23 @@
4646
# self.right = right
4747
classSolution:
4848
defsortedListToBST(self,head:Optional[ListNode])->Optional[TreeNode]:
49+
defdfs(start,end):
50+
nonlocalhead
51+
ifstart>end:
52+
returnNone
53+
mid= (start+end)//2
54+
55+
left=dfs(start,mid-1)
56+
root=TreeNode(head.val)
57+
head=head.next
58+
right=dfs(mid+1,end)
59+
root.left=left
60+
root.right=right
61+
returnroot
62+
counter=0
63+
cur=head
64+
whilecur:
65+
cur=cur.next
66+
counter+=1
67+
returndfs(1,counter)
4968
# leetcode submit region end(Prohibit modification and deletion)

‎script/[110]平衡二叉树.py

Lines changed: 18 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -37,7 +37,7 @@
3737
# 树中的节点数在范围 [0, 5000] 内
3838
# -10⁴ <= Node.val <= 10⁴
3939
#
40-
# Related Topics 树 深度优先搜索 二叉树 👍1075 👎 0
40+
# Related Topics 树 深度优先搜索 二叉树 👍1079 👎 0
4141

4242

4343
# leetcode submit region begin(Prohibit modification and deletion)
@@ -49,4 +49,21 @@
4949
# self.right = right
5050
classSolution:
5151
defisBalanced(self,root:TreeNode)->bool:
52+
defdfs(root):
53+
ifnotroot:
54+
return0
55+
left=dfs(root.left)
56+
right=dfs(root.right)
57+
ifleft==-1orright==-1:
58+
return-1
59+
elifabs(right-left)>1:
60+
return-1
61+
else:
62+
returnmax(left,right)+1
63+
result=dfs(root)
64+
ifresult==-1:
65+
returnFalse
66+
else:
67+
returnTrue
68+
5269
# leetcode submit region end(Prohibit modification and deletion)

‎script/[114]二叉树展开为链表.py

Lines changed: 12 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -55,4 +55,16 @@ def flatten(self, root: TreeNode) -> None:
5555
"""
5656
Do not return anything, modify root in-place instead.
5757
"""
58+
pre=None
59+
defdfs(root):
60+
nonlocalpre
61+
ifnotroot:
62+
returnNone
63+
dfs(root.right)
64+
dfs(root.left)
65+
root.left=None
66+
root.right=pre
67+
pre=root
68+
dfs(root)
69+
returnpre
5870
# leetcode submit region end(Prohibit modification and deletion)

‎script/[129]求根节点到叶节点数字之和.py

Lines changed: 13 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -58,4 +58,17 @@
5858
# self.right = right
5959
classSolution:
6060
defsumNumbers(self,root:TreeNode)->int:
61+
total=0
62+
defdfs(root,path):
63+
nonlocaltotal
64+
ifnotroot.leftandnotroot.right:
65+
path=10*path+root.val
66+
total+=path
67+
return
68+
ifroot.left:
69+
dfs(root.left,10*path+root.val)
70+
ifroot.right:
71+
dfs(root.right,10*path+root.val)
72+
dfs(root,0)
73+
returntotal
6174
# leetcode submit region end(Prohibit modification and deletion)

‎script/[236]二叉树的最近公共祖先.py

Lines changed: 16 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -39,7 +39,7 @@
3939
# p != q
4040
# p 和 q 均存在于给定的二叉树中。
4141
#
42-
# Related Topics 树 深度优先搜索 二叉树 👍1850 👎 0
42+
# Related Topics 树 深度优先搜索 二叉树 👍1854 👎 0
4343

4444

4545
# leetcode submit region begin(Prohibit modification and deletion)
@@ -52,5 +52,20 @@
5252

5353
classSolution:
5454
deflowestCommonAncestor(self,root:'TreeNode',p:'TreeNode',q:'TreeNode')->'TreeNode':
55+
defdfs(root):
56+
#返回的是节点
57+
ifnotroot:
58+
returnNone
59+
ifroot==porroot==q:
60+
returnroot
61+
left=dfs(root.left)
62+
right=dfs(root.right)
63+
ifleftandright:
64+
returnroot
65+
elifleft:
66+
returnleft
67+
else:
68+
returnright
69+
returndfs(root)
5570

5671
# leetcode submit region end(Prohibit modification and deletion)
Lines changed: 65 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,65 @@
1+
# 给定一个 N 叉树，返回其节点值的层序遍历。（即从左到右，逐层遍历）。
2+
#
3+
# 树的序列化输入是用层序遍历，每组子节点都由 null 值分隔（参见示例）。
4+
#
5+
#
6+
#
7+
# 示例 1：
8+
#
9+
#
10+
#
11+
#
12+
# 输入：root = [1,null,3,2,4,null,5,6]
13+
# 输出：[[1],[3,2,4],[5,6]]
14+
#
15+
#
16+
# 示例 2：
17+
#
18+
#
19+
#
20+
#
21+
# 输入：root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,
22+
# null,13,null,null,14]
23+
# 输出：[[1],[2,3,4,5],[6,7,8,9,10],[11,12,13],[14]]
24+
#
25+
#
26+
#
27+
#
28+
# 提示：
29+
#
30+
#
31+
# 树的高度不会超过 1000
32+
# 树的节点总数在 [0, 10^4] 之间
33+
#
34+
# Related Topics 树 广度优先搜索 👍 304 👎 0
35+
36+
37+
# leetcode submit region begin(Prohibit modification and deletion)
38+
"""
39+
# Definition for a Node.
40+
class Node:
41+
def __init__(self, val=None, children=None):
42+
self.val = val
43+
self.children = children
44+
"""
45+
46+
classSolution:
47+
deflevelOrder(self,root:'Node')->List[List[int]]:
48+
ifnotroot:
49+
return []
50+
result= []
51+
stack= [root]
52+
whilestack:
53+
l=len(stack)
54+
tmp= []
55+
foriinrange(l):
56+
node=stack.pop(0)
57+
tmp.append(node.val)
58+
foriinnode.children:
59+
stack.append(i)
60+
result.append(tmp)
61+
returnresult
62+
63+
64+
65+
# leetcode submit region end(Prohibit modification and deletion)

‎script/[450]删除二叉搜索树中的节点.py

Lines changed: 24 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -65,4 +65,28 @@
6565
# self.right = right
6666
classSolution:
6767
defdeleteNode(self,root:Optional[TreeNode],key:int)->Optional[TreeNode]:
68+
defdfs(root):
69+
ifnotroot:
70+
returnNone
71+
ifroot.val==key:
72+
ifnotroot.leftandnotroot.right:
73+
returnNone
74+
elifnotroot.left:
75+
returnroot.right
76+
elifnotroot.right:
77+
returnroot.left
78+
else:
79+
cur=root.right
80+
left=root.left
81+
whilecur.left:
82+
cur=cur.left
83+
cur.left=left
84+
returnroot.right
85+
elifroot.val<key:
86+
root.right=dfs(root.right)
87+
else:
88+
root.left=dfs(root.left )
89+
returnroot
90+
returndfs(root)
91+
6892
# leetcode submit region end(Prohibit modification and deletion)

‎script/[543]二叉树的直径.py

Lines changed: 44 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,44 @@
1+
# 给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。
2+
#
3+
#
4+
#
5+
# 示例 :
6+
# 给定二叉树
7+
#
8+
# 1
9+
# / \
10+
# 2 3
11+
# / \
12+
# 4 5
13+
#
14+
#
15+
# 返回 3, 它的长度是路径 [4,2,1,3] 或者 [5,2,1,3]。
16+
#
17+
#
18+
#
19+
# 注意：两结点之间的路径长度是以它们之间边的数目表示。
20+
# Related Topics 树 深度优先搜索 二叉树 👍 1097 👎 0
21+
22+
23+
# leetcode submit region begin(Prohibit modification and deletion)
24+
# Definition for a binary tree node.
25+
# class TreeNode:
26+
# def __init__(self, val=0, left=None, right=None):
27+
# self.val = val
28+
# self.left = left
29+
# self.right = right
30+
classSolution:
31+
defdiameterOfBinaryTree(self,root:Optional[TreeNode])->int:
32+
maxl=0
33+
defdfs(root):
34+
nonlocalmaxl
35+
ifnotroot:
36+
return0
37+
left=dfs(root.left)
38+
right=dfs(root.right)
39+
maxl=max(maxl,left+right)
40+
returnmax(left,right)+1
41+
dfs(root)
42+
returnmaxl
43+
44+
# leetcode submit region end(Prohibit modification and deletion)
Lines changed: 59 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,59 @@
1+
# 给定一个 N 叉树，找到其最大深度。
2+
#
3+
# 最大深度是指从根节点到最远叶子节点的最长路径上的节点总数。
4+
#
5+
# N 叉树输入按层序遍历序列化表示，每组子节点由空值分隔（请参见示例）。
6+
#
7+
#
8+
#
9+
# 示例 1：
10+
#
11+
#
12+
#
13+
#
14+
# 输入：root = [1,null,3,2,4,null,5,6]
15+
# 输出：3
16+
#
17+
#
18+
# 示例 2：
19+
#
20+
#
21+
#
22+
#
23+
# 输入：root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,
24+
# null,13,null,null,14]
25+
# 输出：5
26+
#
27+
#
28+
#
29+
#
30+
# 提示：
31+
#
32+
#
33+
# 树的深度不会超过 1000 。
34+
# 树的节点数目位于 [0, 10⁴] 之间。
35+
#
36+
# Related Topics 树 深度优先搜索 广度优先搜索 👍 293 👎 0
37+
38+
39+
# leetcode submit region begin(Prohibit modification and deletion)
40+
"""
41+
# Definition for a Node.
42+
class Node:
43+
def __init__(self, val=None, children=None):
44+
self.val = val
45+
self.children = children
46+
"""
47+
48+
classSolution:
49+
defmaxDepth(self,root:'Node')->int:
50+
defdfs(root):
51+
ifnotroot:
52+
return0
53+
depth=0
54+
forchildinroot.children:
55+
depth=max(depth,dfs(child))
56+
returndepth+1
57+
returndfs(root )
58+
59+
# leetcode submit region end(Prohibit modification and deletion)

0 commit comments

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