写在最前
注：由于单版面容不下665道题，因此拆分，之后会单做一个目录。
**答案有误请私信告知，谢谢。
这是由Mono开展的第一个长期项目，会将Leetcode相关习题通过AHKv2实现，每道题会同步贴出相应Python代码。对一些Python程序员而言，可以通过比较，更快迁移到AHK这门语言上。
***引流：请喜欢Python的或是对于人工智能感兴趣的程序员关注我的另一个（大概）每周更新项目《Sinet库》，目前已经迁移了包括Numpy、Pandas和Sklearn在内的大量Python相关函数内容。
***引流2：目前新出一个长期项目，是关于Sinet库的数据类型的代码示例及解析，有兴趣的可以捧个人场。
***引流3：目前新出一个长期项目，是利用Numahk库进行人工智能机器学习模块的示例教学。
更新至第一百一十题 2022.08.07 Mono
第一百零一题 对称二叉树
Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).
给定一棵二叉树，检查它是否是自身的镜像（即围绕其中心对称）。
For example, this binary tree [1,2,2,3,4,4,3] is symmetric:
1
/ \
2 2
/ \ / \
3 4 4 3
But the following [1,2,2,null,3,null,3] is not:
1
/ \
2 2
\ \
3 3
Note:
Bonus points if you could solve it both recursively and iteratively.
注:如果您可以递归和迭代求解，则会获得额外的积分。Python
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def isSymmetric(self, node):
"""
:type root: TreeNode
:rtype: bool
"""
def helper(root, mirror):
if not root and not mirror:
return True
if root and mirror and root.val == mirror.val:
return helper(root.left, mirror.right) and helper(root.right, mirror.left)
return False
return helper(node, node)AutoHotkey
class TreeNode
{
__New(x)
{
this.val := x
this.left := ""
this.right := ""
}
}
class Solution
{
static isSymmetric(node)
{
helper(root, mirror)
{
if not root and not mirror
return True
if root and mirror and root.val == mirror.val
return helper(root.left, mirror.right) and helper(root.right, mirror.left)
return False
}
return helper(node, node)
}
}
; Create TreeNode
a := TreeNode(1)
a_head := a
tmp := TreeNode(2)
a.left := tmp
tmp2 := TreeNode(2)
a.right := tmp2
tmp3 := TreeNode(3)
tmp.left := tmp3
tmp4 := TreeNode(4)
tmp.right := tmp4
tmp5 := TreeNode(4)
tmp2.left := tmp5
tmp6 := TreeNode(3)
tmp2.right := tmp6
b := TreeNode(1)
b_head := b
tmp := TreeNode(2)
b.left := tmp
tmp2 := TreeNode(2)
b.right := tmp2
tmp3 := TreeNode(3)
tmp.right := tmp3
tmp4 := TreeNode(3)
tmp2.right := tmp4
; msgBox Solution.isSymmetric(a_head)
; msgBox Solution.isSymmetric(b_head)第一百零二题 二叉树的层次遍历
Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).
给定一棵二叉树，返回其节点值的水平顺序遍历。（即，从左到右，逐级）。
For example:
Given binary tree [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
return its level order traversal as:
[
[3],
[9,20],
[15,7]
]Python
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
from collections import deque
class Solution(object):
def levelOrder(self, root):
"""
:type root: TreeNode
:rtype: List[List[int]]
"""
if not root:
return []
ans = [[root.val]]
queue = deque([root])
while queue:
levelans = []
for _ in xrange(0, len(queue)):
root = queue.popleft()
if root.left:
levelans.append(root.left.val)
queue.append(root.left)
if root.right:
levelans.append(root.right.val)
queue.append(root.right)
if levelans:
ans.append(levelans)
return ansAutoHotkey
class TreeNode
{
__New(x)
{
this.val := x
this.left := ""
this.right := ""
}
}
class deque
{
__New(arr)
{
this.arr := arr
}
append(item)
{
this.arr.push(item)
}
popleft()
{
Return this.arr.RemoveAt(1)
}
}
class Solution
{
static levelOrder(root)
{
if not root
return []
ans := [[root.val]]
queue := deque([root])
while queue.arr.Length
{
levelans := []
loop queue.arr.Length
{
root := queue.popleft()
if root.left
{
levelans.push(root.left.val)
queue.append(root.left)
}
if root.right
{
levelans.push(root.right.val)
queue.append(root.right)
}
}
if levelans.Length
ans.push(levelans)
}
return ans
}
}
; Create TreeNode
a := TreeNode(3)
a_head := a
tmp := TreeNode(9)
a.left := tmp
tmp2 := TreeNode(20)
a.right := tmp2
tmp3 := TreeNode(15)
tmp2.left := tmp3
tmp4 := TreeNode(7)
tmp2.right := tmp4
; Check Solution
; print Solution.levelOrder(a_head)
Print(Text)
{
msgBox ToString(Text)
}
ToString(Text)
{
Print_Text := ""
if Type(Text) == "Array"
{
Print_Text .= "["
For i in Text
Print_Text .= ToString(i) ","
Print_Text := SubStr(Print_Text, 1, StrLen(Print_Text) - 1)
Print_Text .= "]"
}
else
Print_Text .= Text
Return Print_Text
}第一百零三题 二叉树的锯齿形层序遍历
Given a binary tree, return the zigzag level order traversal of its nodes' values. (ie, from left to right, then right to left for the next level and alternate between).
给定一棵二叉树，返回其节点值的Z字形水平顺序遍历。
（即，从左到右，然后从右到左进入下一层，并在两者之间交替）。
For example:
Given binary tree [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
return its zigzag level order traversal as:
[
[3],
[20,9],
[15,7]
]Python
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
from collections import deque
class Solution(object):
def zigzagLevelOrder(self, root):
"""
:type root: TreeNode
:rtype: List[List[int]]
"""
stack = deque([root])
ans = []
odd = True
while stack:
level = []
for k in xrange(0, len(stack)):
top = stack.popleft()
if top is None:
continue
level.append(top.val)
stack.append(top.left)
stack.append(top.right)
if level:
if odd:
ans.append(level)
else:
ans.append(level[::-1])
odd = not odd
return ansAutoHotkey
class TreeNode
{
__New(x)
{
this.val := x
this.left := ""
this.right := ""
}
}
class deque
{
__New(arr)
{
this.arr := arr
}
append(item)
{
this.arr.push(item)
}
popleft()
{
Return this.arr.RemoveAt(1)
}
}
class Solution
{
static zigzagLevelOrder(root)
{
stack := deque([root])
ans := []
odd := True
while stack.arr.Length
{
level := []
loop stack.arr.Length
{
top := stack.popleft()
if !top
continue
level.push(top.val)
stack.append(top.left)
stack.append(top.right)
}
if level.Length
{
if odd
ans.push(level)
else
{
tmp := []
for i in level
tmp.InsertAt(1, i)
ans.push(tmp)
}
}
odd := not odd
}
return ans
}
}
; Create TreeNode
a := TreeNode(3)
a_head := a
tmp := TreeNode(9)
a.left := tmp
tmp2 := TreeNode(20)
a.right := tmp2
tmp3 := TreeNode(15)
tmp2.left := tmp3
tmp4 := TreeNode(7)
tmp2.right := tmp4
; Check Solution
; print Solution.zigzagLevelOrder(a_head)
Print(Text)
{
msgBox ToString(Text)
}
ToString(Text)
{
Print_Text := ""
if Type(Text) == "Array"
{
Print_Text .= "["
For i in Text
Print_Text .= ToString(i) ","
Print_Text := SubStr(Print_Text, 1, StrLen(Print_Text) - 1)
Print_Text .= "]"
}
else
Print_Text .= Text
Return Print_Text
}第一百零四题 二叉树的最大深度
Given a binary tree, find its maximum depth.
The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.
给定一棵二叉树，求其最大深度。
最大深度是沿从根节点到最远叶节点的最长路径的节点数。Python
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def maxDepth(self, root):
"""
:type root: TreeNode
:rtype: int
"""
if not root:
return 0
return max(self.maxDepth(root.left), self.maxDepth(root.right)) + 1AutoHotkey
class TreeNode
{
__New(x)
{
this.val := x
this.left := ""
this.right := ""
}
}
class Solution
{
static maxDepth(root)
{
if not root
return 0
return max(this.maxDepth(root.left), this.maxDepth(root.right)) + 1
}
}
; Create TreeNode
a := TreeNode(3)
a_head := a
tmp := TreeNode(1)
a.left := tmp
tmp2 := TreeNode(4)
a.right := tmp2
tmp3 := TreeNode(2)
tmp2.left := tmp3
; Check Solution
; msgBox Solution.maxDepth(a_head)第一百零五题 从前序与中序遍历序列构造二叉树
Given preorder and inorder traversal of a tree, construct the binary tree.
Note:
You may assume that duplicates do not exist in the tree.
给定树的前序和中序遍历，构造二叉树。
注:您可以假设树中不存在重复项。Python
class Solution(object):
def buildTree(self, preorder, inorder):
"""
:type preorder: List[int]
:type inorder: List[int]
:rtype: TreeNode
"""
self.preindex = 0
ind = {v:i for i, v in enumerate(inorder)}
head = self.dc(0, len(preorder) - 1, preorder, inorder, ind)
return head
def dc(self, start, end, preorder, inorder, ind):
if start <= end:
mid = ind[preorder[self.preindex]]
self.preindex += 1
root = TreeNode(inorder[mid])
root.left = self.dc(start, mid - 1, preorder, inorder, ind)
root.right = self.dc(mid + 1, end, preorder, inorder, ind)
return rootAutoHotkey
class TreeNode
{
__New(x)
{
this.val := x
this.left := ""
this.right := ""
}
}
class Solution
{
static buildTree(preorder, inorder)
{
this.preindex := 0
ind := map()
for i, v in inorder
ind[v] := i - 1
head := this.dc(0, preorder.Length - 1, preorder, inorder, ind)
return head
}
static dc(start, end, preorder, inorder, ind)
{
if start <= end
{
mid := ind[preorder[this.preindex + 1]]
this.preindex += 1
root := TreeNode(inorder[mid + 1])
root.left := this.dc(start, mid - 1, preorder, inorder, ind)
root.right := this.dc(mid + 1, end, preorder, inorder, ind)
return root
}
}
}
; Check Solution
; arr1 := [3,9,20,15,7]
; arr2 := [9,3,15,20,7]
; msgBox print_treenode(Solution.buildTree(arr1, arr2))
print_treenode(root)
{
res := "None"
if root
{
res := root.val
res .= "->(" print_treenode(root.right) ")"
res := "(" print_treenode(root.left) ")<-" res
}
return res
}第一百零六题 从中序与后序遍历序列构造二叉树
Given inorder and postorder traversal of a tree, construct the binary tree.
Note:
You may assume that duplicates do not exist in the tree.
给定树的中序和后序遍历，构造二叉树。
注:您可以假设树中不存在重复项。Python
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def buildTree(self, inorder, postorder):
"""
:type inorder: List[int]
:type postorder: List[int]
:rtype: TreeNode
"""
if inorder and postorder:
postorder.reverse()
self.index = 0
d = {}
for i in xrange(0, len(inorder)):
d[inorder[i]] = i
return self.dfs(inorder, postorder, 0, len(postorder) - 1, d)
def dfs(self, inorder, postorder, start, end, d):
if start <= end:
root = TreeNode(postorder[self.index])
mid = d[postorder[self.index]]
self.index += 1
root.right = self.dfs(inorder, postorder, mid + 1, end, d)
root.left = self.dfs(inorder, postorder, start, mid - 1, d)
return rootAutoHotkey
class TreeNode
{
__New(x)
{
this.val := x
this.left := ""
this.right := ""
}
}
class Solution
{
static buildTree(inorder, postorder)
{
if inorder.Length and postorder.Length
{
tmp := []
for i in postorder
tmp.InsertAt(1, i)
postorder := tmp
this.index := 0
d := map()
loop inorder.Length
d[inorder[A_Index]] := A_Index - 1
return this.dfs(inorder, postorder, 0, postorder.Length - 1, d)
}
}
static dfs(inorder, postorder, start, end, d)
{
if start <= end
{
root := TreeNode(postorder[this.index + 1])
mid := d[postorder[this.index + 1]]
this.index += 1
root.right := this.dfs(inorder, postorder, mid + 1, end, d)
root.left := this.dfs(inorder, postorder, start, mid - 1, d)
return root
}
}
}
; Check Solution
arr1 := [9,3,15,20,7]
arr2 := [9,15,7,20,3]
; Check Solution
; msgBox print_treenode(Solution.buildTree(arr1, arr2))
print_treenode(root)
{
res := "None"
if root
{
res := root.val
res .= "->(" print_treenode(root.right) ")"
res := "(" print_treenode(root.left) ")<-" res
}
return res
}第一百零七题 二叉树的层次遍历 II
Given a binary tree, return the bottom-up level order traversal of its nodes' values. (ie, from left to right, level by level from leaf to root).
给定一棵二叉树，返回其节点值的自底向上的层次顺序遍历。（即从左到右，从叶到根逐级）。
For example:
Given binary tree [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
return its bottom-up level order traversal as:
[
[15,7],
[9,20],
[3]
]Python
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
from collections import deque
class Solution(object):
def levelOrderBottom(self, root):
"""
:type root: TreeNode
:rtype: List[List[int]]
"""
if not root:
return []
ans = [[root.val]]
queue = deque([root])
while queue:
levelans = []
for _ in xrange(0, len(queue)):
root = queue.popleft()
if root.left:
levelans.append(root.left.val)
queue.append(root.left)
if root.right:
levelans.append(root.right.val)
queue.append(root.right)
if levelans:
ans.append(levelans)
return ans[::-1]AutoHotkey
class TreeNode
{
__New(x)
{
this.val := x
this.left := ""
this.right := ""
}
}
class deque
{
__New(arr)
{
this.arr := arr
}
append(item)
{
this.arr.push(item)
}
popleft()
{
Return this.arr.RemoveAt(1)
}
}
class Solution
{
static levelOrderBottom(root)
{
if not root
return []
ans := [[root.val]]
queue := deque([root])
while queue.arr.Length
{
levelans := []
loop queue.arr.Length
{
root := queue.popleft()
if root.left
{
levelans.push(root.left.val)
queue.append(root.left)
}
if root.right
{
levelans.push(root.right.val)
queue.append(root.right)
}
}
if levelans.Length
ans.push(levelans)
}
tmp := []
for i in ans
tmp.InsertAt(1, i)
return tmp
}
}
; Create TreeNode
a := TreeNode(3)
a_head := a
tmp := TreeNode(9)
a.left := tmp
tmp2 := TreeNode(20)
a.right := tmp2
tmp3 := TreeNode(15)
tmp2.left := tmp3
tmp4 := TreeNode(7)
tmp2.right := tmp4
; Check Solution
; print Solution.levelOrderBottom(a_head)
Print(Text)
{
msgBox ToString(Text)
}
ToString(Text)
{
Print_Text := ""
if Type(Text) == "Array"
{
Print_Text .= "["
For i in Text
Print_Text .= ToString(i) ","
Print_Text := SubStr(Print_Text, 1, StrLen(Print_Text) - 1)
Print_Text .= "]"
}
else
Print_Text .= Text
Return Print_Text
}第一百零八题 将有序数组转化为二叉搜索树
Given an array where elements are sorted in ascending order, convert it to a height balanced BST.
给定元素按升序排序的数组，将其转换为高度平衡的BST。Python
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def sortedArrayToBST(self, nums):
"""
:type nums: List[int]
:rtype: TreeNode
"""
if nums:
midPos = len(nums) / 2
mid = nums[midPos]
root = TreeNode(mid)
root.left = self.sortedArrayToBST(nums[:midPos])
root.right = self.sortedArrayToBST(nums[midPos+1:])
return rootAutoHotkey
class TreeNode
{
__New(x)
{
this.val := x
this.left := ""
this.right := ""
}
}
class Solution
{
static sortedArrayToBST(nums)
{
if nums.Length
{
midPos := nums.Length // 2
mid := nums[midPos + 1]
root := TreeNode(mid)
root.left := this.sortedArrayToBST(cut(nums,,midPos))
root.right := this.sortedArrayToBST(cut(nums,midPos+1))
return root
}
}
}
; Check Solution
; msgBox print_treenode(Solution.sortedArrayToBST([-10,-3,0,5,9]))
cut(arr, start := 0, end := -1)
{
if end == -1
end := arr.Length
tmp := []
for i in arr
{
if A_Index < start + 1
Continue
if A_Index > end
Break
tmp.push(i)
}
return tmp
}
print_treenode(root)
{
res := "None"
if root
{
res := root.val
res .= "->(" print_treenode(root.right) ")"
res := "(" print_treenode(root.left) ")<-" res
}
return res
}第一百零九题 有序链表转换二叉搜索树
Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.
给定元素按升序排序的单链表，将其转换为高度平衡的BST。Python
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def sortedListToBST(self, head):
"""
:type head: ListNode
:rtype: TreeNode
"""
if head:
pre = None
slow = fast = head
while fast and fast.next:
pre = slow
slow = slow.next
fast = fast.next.next
root = TreeNode(slow.val)
if pre:
pre.next = None
root.left = self.sortedListToBST(head)
root.right = self.sortedListToBST(slow.next)
return rootAutoHotkey
class ListNode
{
__New(x)
{
this.val := x
this.next := ""
}
}
class TreeNode
{
__New(x)
{
this.val := x
this.left := ""
this.right := ""
}
}
class Solution
{
static sortedListToBST(head)
{
if head
{
pre := ""
slow := fast := head
while fast and fast.next
{
pre := slow
slow := slow.next
fast := fast.next.next
}
root := TreeNode(slow.val)
if pre
{
pre.next := ""
root.left := this.sortedListToBST(head)
}
root.right := this.sortedListToBST(slow.next)
return root
}
}
}
; Create List_Node
a := ListNode(10)
a_head := a
arr := [-3,0,5,9]
Loop arr.length
{
temp := ListNode(arr[A_Index])
a.next := temp
a := a.next
}
; Check Solution
; msgBox print_treenode(Solution.sortedListToBST(a_head))
print_treenode(root)
{
res := "None"
if root
{
res := root.val
res .= "->(" print_treenode(root.right) ")"
res := "(" print_treenode(root.left) ")<-" res
}
return res
}第一百一十题 平衡二叉树
Given a binary tree, determine if it is height-balanced.
For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.
给定一棵二叉树，确定它是否高度平衡。
对于这个问题，高度平衡二叉树被定义为每个节点的两个子树深度相差不超过1的二叉树。Python
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def isBalanced(self, root):
"""
:type root: TreeNode
:rtype: bool
"""
def dfs(p):
if not p:
return 0
left = dfs(p.left)
right = dfs(p.right)
if left == -1 or right == -1:
return -1
if abs(left - right) > 1:
return -1
return 1 + max(left, right)
if dfs(root) == -1:
return False
return TrueAutoHotkey
class TreeNode
{
__New(x)
{
this.val := x
this.left := ""
this.right := ""
}
}
class Solution
{
static isBalanced(root)
{
dfs(p)
{
if not p
return 0
left := dfs(p.left)
right := dfs(p.right)
if left == -1 or right == -1
return -1
if abs(left - right) > 1
return -1
return 1 + max(left, right)
}
if dfs(root) == -1
return False
return True
}
}
; Create TreeNode
a := TreeNode(3)
a_head := a
tmp := TreeNode(9)
a.left := tmp
tmp2 := TreeNode(20)
a.right := tmp2
tmp3 := TreeNode(15)
tmp2.left := tmp3
tmp4 := TreeNode(7)
tmp2.right := tmp4
b := TreeNode(1)
b_head := b
tmp := TreeNode(2)
b.left := tmp
tmp2 := TreeNode(2)
b.right := tmp2
tmp3 := TreeNode(3)
tmp.left := tmp3
tmp4 := TreeNode(3)
tmp.right := tmp4
tmp5 := TreeNode(4)
tmp3.left := tmp5
tmp6 := TreeNode(4)
tmp3.right := tmp6
; Check Solution
; msgBox Solution.isBalanced(a_head)
; msgBox Solution.isBalanced(b_head)
