leetcode刷题之深度搜索

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