Skip to content

Commit ef7e407

Browse files
author
liningrui
committed
add new solutions
1 parent 579ed13 commit ef7e407

33 files changed

+2044
-0
lines changed

‎script/[100]相同的树.py

Lines changed: 59 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,59 @@
1+
# 给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。
2+
#
3+
# 如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。
4+
#
5+
#
6+
#
7+
# 示例 1：
8+
#
9+
#
10+
# 输入：p = [1,2,3], q = [1,2,3]
11+
# 输出：true
12+
#
13+
#
14+
# 示例 2：
15+
#
16+
#
17+
# 输入：p = [1,2], q = [1,null,2]
18+
# 输出：false
19+
#
20+
#
21+
# 示例 3：
22+
#
23+
#
24+
# 输入：p = [1,2,1], q = [1,1,2]
25+
# 输出：false
26+
#
27+
#
28+
#
29+
#
30+
# 提示：
31+
#
32+
#
33+
# 两棵树上的节点数目都在范围 [0, 100] 内
34+
# -10⁴ <= Node.val <= 10⁴
35+
#
36+
# Related Topics 树 深度优先搜索 广度优先搜索 二叉树 👍 862 👎 0
37+
38+
39+
# leetcode submit region begin(Prohibit modification and deletion)
40+
# Definition for a binary tree node.
41+
# class TreeNode:
42+
# def __init__(self, val=0, left=None, right=None):
43+
# self.val = val
44+
# self.left = left
45+
# self.right = right
46+
class Solution:
47+
def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
48+
def helper(p,q):
49+
if not p and not q:
50+
return True
51+
elif not p:
52+
return False
53+
elif not q:
54+
return False
55+
elif p.val!=q.val:
56+
return False
57+
return helper(p.right, q.right) and helper(p.left, q.left)
58+
return helper(p,q)
59+
# leetcode submit region end(Prohibit modification and deletion)

‎script/[101]对称二叉树.py

Lines changed: 54 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,54 @@
1+
# 给你一个二叉树的根节点 root ， 检查它是否轴对称。
2+
#
3+
#
4+
#
5+
# 示例 1：
6+
#
7+
#
8+
# 输入：root = [1,2,2,3,4,4,3]
9+
# 输出：true
10+
#
11+
#
12+
# 示例 2：
13+
#
14+
#
15+
# 输入：root = [1,2,2,null,3,null,3]
16+
# 输出：false
17+
#
18+
#
19+
#
20+
#
21+
# 提示：
22+
#
23+
#
24+
# 树中节点数目在范围 [1, 1000] 内
25+
# -100 <= Node.val <= 100
26+
#
27+
#
28+
#
29+
#
30+
# 进阶：你可以运用递归和迭代两种方法解决这个问题吗？
31+
# Related Topics 树 深度优先搜索 广度优先搜索 二叉树 👍 2013 👎 0
32+
33+
34+
# leetcode submit region begin(Prohibit modification and deletion)
35+
# Definition for a binary tree node.
36+
# class TreeNode:
37+
# def __init__(self, val=0, left=None, right=None):
38+
# self.val = val
39+
# self.left = left
40+
# self.right = right
41+
class Solution:
42+
def isSymmetric(self, root: Optional[TreeNode]) -> bool:
43+
def helper(p,q):
44+
if not p and not q:
45+
return True
46+
elif not p:
47+
return False
48+
elif not q:
49+
return False
50+
elif p.val!=q.val:
51+
return False
52+
return helper(p.left, q.right) and helper(p.right, q.left)
53+
return helper(root.left, root.right)
54+
# leetcode submit region end(Prohibit modification and deletion)

‎script/[102]二叉树的层序遍历.py

Lines changed: 64 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,64 @@
1+
# 给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。
2+
#
3+
#
4+
#
5+
# 示例 1：
6+
#
7+
#
8+
# 输入：root = [3,9,20,null,null,15,7]
9+
# 输出：[[3],[9,20],[15,7]]
10+
#
11+
#
12+
# 示例 2：
13+
#
14+
#
15+
# 输入：root = [1]
16+
# 输出：[[1]]
17+
#
18+
#
19+
# 示例 3：
20+
#
21+
#
22+
# 输入：root = []
23+
# 输出：[]
24+
#
25+
#
26+
#
27+
#
28+
# 提示：
29+
#
30+
#
31+
# 树中节点数目在范围 [0, 2000] 内
32+
# -1000 <= Node.val <= 1000
33+
#
34+
# Related Topics 树 广度优先搜索 二叉树 👍 1391 👎 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 levelOrder(self, root: TreeNode) -> List[List[int]]:
46+
if not root:
47+
return []
48+
result = []
49+
stack = [root]
50+
while stack:
51+
l = len(stack)
52+
tmp = []
53+
for i in range(l):
54+
node= stack.pop(0) #注意是pop left
55+
tmp.append(node.val)
56+
if node.left:
57+
stack.append(node.left)
58+
if node.right:
59+
stack.append(node.right)
60+
result.append(tmp)
61+
return result
62+
63+
64+
# leetcode submit region end(Prohibit modification and deletion)

‎script/[103]二叉树的锯齿形层序遍历.py

Lines changed: 67 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,67 @@
1+
# 给你二叉树的根节点 root ，返回其节点值的 锯齿形层序遍历 。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。
2+
#
3+
#
4+
#
5+
# 示例 1：
6+
#
7+
#
8+
# 输入：root = [3,9,20,null,null,15,7]
9+
# 输出：[[3],[20,9],[15,7]]
10+
#
11+
#
12+
# 示例 2：
13+
#
14+
#
15+
# 输入：root = [1]
16+
# 输出：[[1]]
17+
#
18+
#
19+
# 示例 3：
20+
#
21+
#
22+
# 输入：root = []
23+
# 输出：[]
24+
#
25+
#
26+
#
27+
#
28+
# 提示：
29+
#
30+
#
31+
# 树中节点数目在范围 [0, 2000] 内
32+
# -100 <= Node.val <= 100
33+
#
34+
# Related Topics 树 广度优先搜索 二叉树 👍 668 👎 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 zigzagLevelOrder(self, root: TreeNode) -> List[List[int]]:
46+
if not root:
47+
return []
48+
result = []
49+
stack = [root]
50+
flag = 1
51+
while stack:
52+
l = len(stack)
53+
tmp = []
54+
for i in range(l):
55+
node= stack.pop(0) #注意是pop left
56+
tmp.append(node.val)
57+
if node.left:
58+
stack.append(node.left)
59+
if node.right:
60+
stack.append(node.right)
61+
if flag>0:
62+
result.append(tmp)
63+
else:
64+
result.append(tmp[::-1])
65+
flag*=-1
66+
return result
67+
# leetcode submit region end(Prohibit modification and deletion)

‎script/[104]二叉树的最大深度.py

Lines changed: 36 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,36 @@
1+
# 给定一个二叉树，找出其最大深度。
2+
#
3+
# 二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
4+
#
5+
# 说明: 叶子节点是指没有子节点的节点。
6+
#
7+
# 示例：
8+
# 给定二叉树 [3,9,20,null,null,15,7]，
9+
#
10+
# 3
11+
# / \
12+
# 9 20
13+
# / \
14+
# 15 7
15+
#
16+
# 返回它的最大深度 3 。
17+
# Related Topics 树 深度优先搜索 广度优先搜索 二叉树 👍 1300 👎 0
18+
19+
20+
# leetcode submit region begin(Prohibit modification and deletion)
21+
# Definition for a binary tree node.
22+
# class TreeNode:
23+
# def __init__(self, val=0, left=None, right=None):
24+
# self.val = val
25+
# self.left = left
26+
# self.right = right
27+
class Solution:
28+
def maxDepth(self, root: Optional[TreeNode]) -> int:
29+
def dfs(root):
30+
if not root:
31+
return 0
32+
left= dfs(root.left)
33+
right = dfs(root.right)
34+
return max(left,right)+1
35+
return dfs(root)
36+
# leetcode submit region end(Prohibit modification and deletion)

‎script/[105]从前序与中序遍历序列构造二叉树.py

Lines changed: 60 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,60 @@
1+
# 给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并
2+
# 返回其根节点。
3+
#
4+
#
5+
#
6+
# 示例 1:
7+
#
8+
#
9+
# 输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
10+
# 输出: [3,9,20,null,null,15,7]
11+
#
12+
#
13+
# 示例 2:
14+
#
15+
#
16+
# 输入: preorder = [-1], inorder = [-1]
17+
# 输出: [-1]
18+
#
19+
#
20+
#
21+
#
22+
# 提示:
23+
#
24+
#
25+
# 1 <= preorder.length <= 3000
26+
# inorder.length == preorder.length
27+
# -3000 <= preorder[i], inorder[i] <= 3000
28+
# preorder 和 inorder 均 无重复 元素
29+
# inorder 均出现在 preorder
30+
# preorder 保证 为二叉树的前序遍历序列
31+
# inorder 保证 为二叉树的中序遍历序列
32+
#
33+
# Related Topics 树 数组 哈希表 分治 二叉树 👍 1663 👎 0
34+
35+
36+
# leetcode submit region begin(Prohibit modification and deletion)
37+
# Definition for a binary tree node.
38+
# class TreeNode:
39+
# def __init__(self, val=0, left=None, right=None):
40+
# self.val = val
41+
# self.left = left
42+
# self.right = right
43+
class Solution:
44+
def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
45+
def dfs(left, right):
46+
if left>right:
47+
return None
48+
val = preorder.pop(0)
49+
root = TreeNode(val)
50+
pos = inorder.index(val)
51+
root.left = dfs(left, pos-1)
52+
root.right = dfs(pos+1, right)
53+
return root
54+
55+
return dfs(0, len(preorder)-1)
56+
57+
58+
59+
60+
# leetcode submit region end(Prohibit modification and deletion)

0 commit comments

Comments
 (0)