leetcode刷题,使用python
1,二叉树的中序遍历 —— 0094 中序遍历
给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。
# Definition for a binary tree node.
from typing import Optional
from typing import List
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
res = []
def InorderTravel(p):
if not p:
return
InorderTravel(p.left)
res.append(p.val)
InorderTravel(p.right)
InorderTravel(root)
return res
root = TreeNode(1)
a1 = TreeNode(2)
a2 = TreeNode(3)
root.right = a1
a1.left = a2
S = Solution()
print(S.inorderTraversal(root))
2, 验证二叉搜索树 —— 0098 递归
给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。
有效 二叉搜索树定义如下：
节点的左子树只包含 小于 当前节点的数。
节点的右子树只包含 大于 当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。
# Definition for a binary tree node.
from typing import Optional
from typing import List
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def isValidBST(self, root: Optional[TreeNode]) -> bool:
def Valid(p, lower=float('-inf'), upper=float('inf'))->bool:
if not p:
return True
val = p.val
if val <=lower or val >= upper:
return False
if not Valid(p.right, val, upper):
return False
if not Valid(p.left, lower, val):
return False
return True
return Valid(root)
root = TreeNode(2)
a1 = TreeNode(1)
a2 = TreeNode(3)
root.left = a1
root.right = a2
S = Solution()
print(S.isValidBST(root))
3, 恢复二叉搜索树 —— 0099 显式中序遍历
给你二叉搜索树的根节点 root ，该树中的 恰好 两个节点的值被错误地交换。请在不改变其结构的情况下，恢复这棵树 。
image.png
# Definition for a binary tree node.
from typing import Optional
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
#
class Solution:
def recoverTree(self, root: Optional[TreeNode]) -> None:
"""
Do not return anything, modify root in-place instead.
"""
def inorder(root, res):
if not root:
return None
inorder(root.left, res)
res.append(root.val)
inorder(root.right, res)
return res
def findTwoSwapped(nums, swapper):
index = -1
index2 = -1
indexs = []
for i in range(len(nums)-1):
if nums[i] > nums[i+1]:
indexs.append(i)
# 这种情况是相邻的结点有问题
if len(indexs) == 1:
swapper.append(nums[indexs[0]])
swapper.append(nums[indexs[0]+1])
elif len(indexs) == 2:
swapper.append(nums[indexs[0]])
swapper.append(nums[indexs[1]+1])
return swapper
def recover(root, count, x, y):
if not root:
return
if count<=0:
return
if root.val == x:
root.val = y
count -= 1
elif root.val == y:
root.val = x
count -= 1
recover(root.left, count, x, y)
recover(root.right, count, x, y)
nums = inorder(root, [])
# print(nums)
swapper = findTwoSwapped(nums, [])
# print(swapper)
recover(root, 2, swapper[0], swapper[1])
nums2 = inorder(root, [])
# print(nums2)
root = TreeNode(1)
a1 = TreeNode(3)
a2 = TreeNode(2)
root.left = a1
a1.right = a2
S = Solution()
S.recoverTree(root)
4, 路径总和 II —— 0113 深度搜索
给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。
叶子节点 是指没有子节点的节点。
image.png
# Definition for a binary tree node.
from typing import List
from typing import Optional
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def pathSum(self, root: Optional[TreeNode], targetSum: int) -> List[List[int]]:
res = []
path = []
def dfs(node, target):
if not node:
return
path.append(node.val)
target -= node.val
if not node.left and not node.right and target == 0:
# print(path)
res.append(path[:])
dfs(node.left, target)
dfs(node.right, target)
path.pop()
dfs(root, targetSum)
# print(res)
# print(path)
return res
root = TreeNode(5)
a1 = TreeNode(4)
a2 = TreeNode(8)
a3 = TreeNode(11)
a4 = TreeNode(13)
a5 = TreeNode(4)
a6 = TreeNode(7)
a7 = TreeNode(2)
a8 = TreeNode(5)
a9 = TreeNode(1)
root.left = a1
root.right = a2
a1.left = a3
a2.left = a4
a2.right = a5
a3.left = a6
a3.right = a7
a5.left = a8
a5.right = a9
S = Solution()
print(S.pathSum(root, 22))
5, 二叉树展开为链表 —— 0114 前序遍历
给你二叉树的根结点 root ，请你将它展开为一个单链表：
展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。
展开后的单链表应该与二叉树 先序遍历 顺序相同。
image.png
# Definition for a binary tree node.
from typing import Optional
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def flatten(self, root: Optional[TreeNode]) -> None:
preorderList = []
def preorderTraversal(root: TreeNode):
if not root:
return
preorderList.append(root)
preorderTraversal(root.left)
preorderTraversal(root.right)
preorderTraversal(root)
n = len(preorderList)
for i in range(1, n):
pre, cur = preorderList[i-1], preorderList[i]
pre.left = None
pre.right = cur
return root
网友评论