leetcode刷題,使用python
1,二叉樹的中序遍歷 —— 0094 中序遍歷
給定一個二叉樹的根節(jié)點 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 遞歸
給你一個二叉樹的根節(jié)點 root ，判斷其是否是一個有效的二叉搜索樹。
有效 二叉搜索樹定義如下：
節(jié)點的左子樹只包含 小于 當(dāng)前節(jié)點的數(shù)。
節(jié)點的右子樹只包含 大于 當(dāng)前節(jié)點的數(shù)。
所有左子樹和右子樹自身必須也是二叉搜索樹。
# 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, 恢復(fù)二叉搜索樹 —— 0099 顯式中序遍歷
給你二叉搜索樹的根節(jié)點 root ，該樹中的 恰好 兩個節(jié)點的值被錯誤地交換。請在不改變其結(jié)構(gòu)的情況下，恢復(fù)這棵樹 。
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)
# 這種情況是相鄰的結(jié)點有問題
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 深度搜索
給你二叉樹的根節(jié)點 root 和一個整數(shù)目標(biāo)和 targetSum ，找出所有 從根節(jié)點到葉子節(jié)點 路徑總和等于給定目標(biāo)和的路徑。
葉子節(jié)點 是指沒有子節(jié)點的節(jié)點。
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 前序遍歷
給你二叉樹的根結(jié)點 root ，請你將它展開為一個單鏈表：
展開后的單鏈表應(yīng)該同樣使用 TreeNode ，其中 right 子指針指向鏈表中下一個結(jié)點，而左子指針始終為 null 。
展開后的單鏈表應(yīng)該與二叉樹 先序遍歷 順序相同。
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
6, 求根節(jié)點到葉節(jié)點數(shù)字之和 —— 0129 深度搜索
給你一個二叉樹的根節(jié)點 root ，樹中每個節(jié)點都存放有一個 0 到 9 之間的數(shù)字。
每條從根節(jié)點到葉節(jié)點的路徑都代表一個數(shù)字：
例如，從根節(jié)點到葉節(jié)點的路徑 1 -> 2 -> 3 表示數(shù)字 123 。
計算從根節(jié)點到葉節(jié)點生成的 所有數(shù)字之和 。
葉節(jié)點 是指沒有子節(jié)點的節(jié)點。
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 sumNumbers(self, root: Optional[TreeNode]) -> int:
if not root:
return 0
def dfs(node, tmpValue):
if not node:
return 0
total = tmpValue*10 + node.val
if node.right == None and node.left == None:
return total
if node.left or node.right:
return dfs(node.left, total) + dfs(node.right, total)
return dfs(root, 0)
S = Solution()
a = TreeNode(1)
b = TreeNode(2)
c = TreeNode(3)
a.left = b
a.right = c
print(S.sumNumbers(a))
