Skip to content

Commit 3e45eec

Browse files
author
liningrui
committed
add new solutions
1 parent cc2e114 commit 3e45eec

20 files changed

+1100
-0
lines changed

‎script/[222]完全二叉树的节点个数.py

Lines changed: 17 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -51,4 +51,21 @@
5151
# self.right = right
5252
class Solution:
5353
def countNodes(self, root: TreeNode) -> int:
54+
def dfs(root):
55+
if not root:
56+
return 0
57+
lh = 0
58+
rh = 0
59+
left = root
60+
right = root
61+
while left:
62+
left = left.left
63+
lh +=1
64+
while right:
65+
right = right.right
66+
rh+=1
67+
if lh==rh:
68+
return 2 ** lh - 1
69+
return dfs(root.left) + dfs(root.right) +1
70+
return dfs(root)
5471
# leetcode submit region end(Prohibit modification and deletion)

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

Lines changed: 8 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -43,5 +43,13 @@
4343

4444
class Solution:
4545
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
46+
l = min(p.val, q.val)
47+
r = max(p.val, q.val)
48+
while root and (root.val<l or root.val>r):
49+
if root.val<l:
50+
root = root.right
51+
else:
52+
root = root.left
53+
return root
4654

4755
# leetcode submit region end(Prohibit modification and deletion)

‎script/[331]验证二叉树的前序序列化.py

Lines changed: 56 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,56 @@
1+
# 序列化二叉树的一种方法是使用 前序遍历 。当我们遇到一个非空节点时，我们可以记录下这个节点的值。如果它是一个空节点，我们可以使用一个标记值记录，例如 #。
2+
#
3+
#
4+
#
5+
#
6+
# 例如，上面的二叉树可以被序列化为字符串 "9,3,4,#,#,1,#,#,2,#,6,#,#"，其中 # 代表一个空节点。
7+
#
8+
# 给定一串以逗号分隔的序列，验证它是否是正确的二叉树的前序序列化。编写一个在不重构树的条件下的可行算法。
9+
#
10+
# 保证 每个以逗号分隔的字符或为一个整数或为一个表示 null 指针的 '#' 。
11+
#
12+
# 你可以认为输入格式总是有效的
13+
#
14+
#
15+
# 例如它永远不会包含两个连续的逗号，比如 "1,,3" 。
16+
#
17+
#
18+
# 注意：不允许重建树。
19+
#
20+
#
21+
#
22+
# 示例 1:
23+
#
24+
#
25+
# 输入: preorder = "9,3,4,#,#,1,#,#,2,#,6,#,#"
26+
# 输出: true
27+
#
28+
# 示例 2:
29+
#
30+
#
31+
# 输入: preorder = "1,#"
32+
# 输出: false
33+
#
34+
#
35+
# 示例 3:
36+
#
37+
#
38+
# 输入: preorder = "9,#,#,1"
39+
# 输出: false
40+
#
41+
#
42+
#
43+
#
44+
# 提示:
45+
#
46+
#
47+
# 1 <= preorder.length <= 10⁴
48+
# preorder 由以逗号 “，” 分隔的 [0,100] 范围内的整数和 “#” 组成
49+
#
50+
# Related Topics 栈 树 字符串 二叉树 👍 393 👎 0
51+
52+
53+
# leetcode submit region begin(Prohibit modification and deletion)
54+
class Solution:
55+
def isValidSerialization(self, preorder: str) -> bool:
56+
# leetcode submit region end(Prohibit modification and deletion)

‎script/[404]左叶子之和.py

Lines changed: 57 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,57 @@
1+
# 给定二叉树的根节点 root ，返回所有左叶子之和。
2+
#
3+
#
4+
#
5+
# 示例 1：
6+
#
7+
#
8+
#
9+
#
10+
# 输入: root = [3,9,20,null,null,15,7]
11+
# 输出: 24
12+
# 解释: 在这个二叉树中，有两个左叶子，分别是 9 和 15，所以返回 24
13+
#
14+
#
15+
# 示例 2:
16+
#
17+
#
18+
# 输入: root = [1]
19+
# 输出: 0
20+
#
21+
#
22+
#
23+
#
24+
# 提示:
25+
#
26+
#
27+
# 节点数在 [1, 1000] 范围内
28+
# -1000 <= Node.val <= 1000
29+
#
30+
#
31+
#
32+
# Related Topics 树 深度优先搜索 广度优先搜索 二叉树 👍 479 👎 0
33+
34+
35+
# leetcode submit region begin(Prohibit modification and deletion)
36+
# Definition for a binary tree node.
37+
# class TreeNode:
38+
# def __init__(self, val=0, left=None, right=None):
39+
# self.val = val
40+
# self.left = left
41+
# self.right = right
42+
class Solution:
43+
def sumOfLeftLeaves(self, root: Optional[TreeNode]) -> int:
44+
total = 0
45+
def dfs(root):
46+
nonlocal total
47+
if not root:
48+
return
49+
if root.left and not root.left.left and not root.left.right:
50+
total+=root.left.val
51+
dfs(root.left)
52+
dfs(root.right)
53+
54+
dfs(root)
55+
return total
56+
57+
# leetcode submit region end(Prohibit modification and deletion)

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

Lines changed: 68 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,68 @@
1+
# 给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的
2+
# 根节点的引用。
3+
#
4+
# 一般来说，删除节点可分为两个步骤：
5+
#
6+
#
7+
# 首先找到需要删除的节点；
8+
# 如果找到了，删除它。
9+
#
10+
#
11+
#
12+
#
13+
# 示例 1:
14+
#
15+
#
16+
#
17+
#
18+
# 输入：root = [5,3,6,2,4,null,7], key = 3
19+
# 输出：[5,4,6,2,null,null,7]
20+
# 解释：给定需要删除的节点值是 3，所以我们首先找到 3 这个节点，然后删除它。
21+
# 一个正确的答案是 [5,4,6,2,null,null,7], 如下图所示。
22+
# 另一个正确答案是 [5,2,6,null,4,null,7]。
23+
#
24+
#
25+
#
26+
#
27+
# 示例 2:
28+
#
29+
#
30+
# 输入: root = [5,3,6,2,4,null,7], key = 0
31+
# 输出: [5,3,6,2,4,null,7]
32+
# 解释: 二叉树不包含值为 0 的节点
33+
#
34+
#
35+
# 示例 3:
36+
#
37+
#
38+
# 输入: root = [], key = 0
39+
# 输出: []
40+
#
41+
#
42+
#
43+
# 提示:
44+
#
45+
#
46+
# 节点数的范围 [0, 10⁴].
47+
# -10⁵ <= Node.val <= 10⁵
48+
# 节点值唯一
49+
# root 是合法的二叉搜索树
50+
# -10⁵ <= key <= 10⁵
51+
#
52+
#
53+
#
54+
#
55+
# 进阶： 要求算法时间复杂度为 O(h)，h 为树的高度。
56+
# Related Topics 树 二叉搜索树 二叉树 👍 907 👎 0
57+
58+
59+
# leetcode submit region begin(Prohibit modification and deletion)
60+
# Definition for a binary tree node.
61+
# class TreeNode:
62+
# def __init__(self, val=0, left=None, right=None):
63+
# self.val = val
64+
# self.left = left
65+
# self.right = right
66+
class Solution:
67+
def deleteNode(self, root: Optional[TreeNode], key: int) -> Optional[TreeNode]:
68+
# leetcode submit region end(Prohibit modification and deletion)

‎script/[501]二叉搜索树中的众数.py

Lines changed: 81 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,81 @@
1+
# 给你一个含重复值的二叉搜索树（BST）的根节点 root ，找出并返回 BST 中的所有 众数（即，出现频率最高的元素）。
2+
#
3+
# 如果树中有不止一个众数，可以按 任意顺序 返回。
4+
#
5+
# 假定 BST 满足如下定义：
6+
#
7+
#
8+
# 结点左子树中所含节点的值 小于等于 当前节点的值
9+
# 结点右子树中所含节点的值 大于等于 当前节点的值
10+
# 左子树和右子树都是二叉搜索树
11+
#
12+
#
13+
#
14+
#
15+
# 示例 1：
16+
#
17+
#
18+
# 输入：root = [1,null,2,2]
19+
# 输出：[2]
20+
#
21+
#
22+
# 示例 2：
23+
#
24+
#
25+
# 输入：root = [0]
26+
# 输出：[0]
27+
#
28+
#
29+
#
30+
#
31+
# 提示：
32+
#
33+
#
34+
# 树中节点的数目在范围 [1, 10⁴] 内
35+
# -10⁵ <= Node.val <= 10⁵
36+
#
37+
#
38+
#
39+
#
40+
# 进阶：你可以不使用额外的空间吗？（假设由递归产生的隐式调用栈的开销不被计算在内）
41+
# Related Topics 树 深度优先搜索 二叉搜索树 二叉树 👍 486 👎 0
42+
43+
44+
# leetcode submit region begin(Prohibit modification and deletion)
45+
# Definition for a binary tree node.
46+
# class TreeNode:
47+
# def __init__(self, val=0, left=None, right=None):
48+
# self.val = val
49+
# self.left = left
50+
# self.right = right
51+
class Solution:
52+
def findMode(self, root: TreeNode) -> List[int]:
53+
counter = 0
54+
maxcount = 0
55+
mode = []
56+
pre = None
57+
58+
def inorder(root):
59+
nonlocal pre, mode, counter, maxcount
60+
if not root:
61+
return
62+
inorder(root.left)
63+
if pre is None:
64+
pre = root.val
65+
counter=1
66+
elif root.val==pre:
67+
counter+=1
68+
else:
69+
counter=1
70+
pre = root.val
71+
if counter > maxcount:
72+
mode = [root.val]
73+
maxcount = counter
74+
elif counter == maxcount:
75+
mode.append(root.val)
76+
inorder(root.right)
77+
78+
inorder(root)
79+
return mode
80+
81+
# leetcode submit region end(Prohibit modification and deletion)

‎script/[513]找树左下角的值.py

Lines changed: 59 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,59 @@
1+
2+
# 给定一个二叉树的 根节点 root，请找出该二叉树的 最底层 最左边 节点的值。
3+
#
4+
# 假设二叉树中至少有一个节点。
5+
#
6+
#
7+
#
8+
# 示例 1:
9+
#
10+
#
11+
#
12+
#
13+
# 输入: root = [2,1,3]
14+
# 输出: 1
15+
#
16+
#
17+
# 示例 2:
18+
#
19+
#
20+
#
21+
#
22+
# 输入: [1,2,3,4,null,5,6,null,null,7]
23+
# 输出: 7
24+
#
25+
#
26+
#
27+
#
28+
# 提示:
29+
#
30+
#
31+
# 二叉树的节点个数的范围是 [1,10⁴]
32+
# -2³¹ <= Node.val <= 2³¹ - 1
33+
#
34+
# Related Topics 树 深度优先搜索 广度优先搜索 二叉树 👍 358 👎 0
35+
36+
37+
# leetcode submit region begin(Prohibit modification and deletion)
38+
# Definition for a binary tree node.
39+
# class TreeNode:
40+
# def __init__(self, val=0, left=None, right=None):
41+
# self.val = val
42+
# self.left = left
43+
# self.right = right
44+
class Solution:
45+
def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:
46+
left = None
47+
stack = [root]
48+
while stack:
49+
l = len(stack)
50+
for i in range(l):
51+
node = stack.pop(0)
52+
if node.left:
53+
stack.append(node.left)
54+
if node.right:
55+
stack.append(node.right)
56+
if i==0:
57+
left = node
58+
return left.val
59+
# leetcode submit region end(Prohibit modification and deletion)

0 commit comments

Comments
 (0)