月度归档： 2022年1月

给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。

叶子节点 是指没有子节点的节点。

示例 1：

输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
输出：[[5,4,11,2],[5,8,4,5]]

示例 2：

输入：root = [1,2,3], targetSum = 5
输出：[]

示例 3：

输入：root = [1,2], targetSum = 0
输出：[]

# [113] 路径总和 II
#

# @lc code=start
# Definition for a binary tree node.
# 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=list()
        rev=list()
        
        def subisBalanced(root,deep,target,rev):
            if  root.left==None and root.right==None and deep==target:   
                res.append(rev)
                return 
            if root.left!=None:
                deepl=deep+ root.left.val
                
                subisBalanced(root.left,deepl,target,rev+ [root.left.val])

                
            if  root.right!=None:
                deepr=deep+root.right.val
               
                subisBalanced(root.right,deepr,target,rev+[root.right.val])

        if root==None:
            return []
        else: 
            rev.append(root.val)
            subisBalanced(root,root.val, targetSum,rev)
            return res
        
# @lc code=end

给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。如果存在，返回 true ；否则，返回 false 。

叶子节点 是指没有子节点的节点。

#
# @lc app=leetcode.cn id=112 lang=python3
#
# [112] 路径总和
#

# @lc code=start
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
        def subisBalanced(root,deep,target):
            if root.left!=None:
                deepl=deep+root.left.val
                if subisBalanced(root.left,deepl,target):
                    return True            
            if  root.right!=None:
                deepr=deep+root.right.val 
                if subisBalanced(root.right,deepr,target):
                    return True
            
            if  root.left==None and root.right==None and deep==target:    
                return True
        if root==None:
            return False
        else:
            if subisBalanced(root,root.val,targetSum)==True:
                return True
            else:
                return False

# @lc code=end

给定一个二叉树，找出其最小深度。

最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

说明：叶子节点是指没有子节点的节点。

示例 1：

输入：root = [3,9,20,null,null,15,7]
输出：2

示例 2：

输入：root = [2,null,3,null,4,null,5,null,6]
输出：5

提示：

• 树中节点数的范围在 [0, 105] 内
• -1000 <= Node.val <= 1000

# [111] 二叉树的最小深度
#

# @lc code=start
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def minDepth(self, root: TreeNode) -> int:
        res=list()
        def subisBalanced(root,deep):
            if root.left!=None:
                deepl=deep+1 
                subisBalanced(root.left,deepl)
            
                
            if  root.right!=None:
                deepr=deep+1 
                subisBalanced(root.right,deepr)
            
            if  root.left==None and root.right==None:
                res.append(deep)
                return 
        if root==None:
            return 0
        subisBalanced(root,1)
        return min(res)
# @lc code=end

给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 高度平衡 二叉搜索树。

高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。

示例 1：

输入：nums = [-10,-3,0,5,9]
输出：[0,-3,9,-10,null,5]
解释：[0,-10,5,null,-3,null,9] 也将被视为正确答案：

示例 2：

输入：nums = [1,3]
输出：[3,1]
解释：[1,3] 和 [3,1] 都是高度平衡二叉搜索树。

# @lc app=leetcode.cn id=108 lang=python3
#
# [108] 将有序数组转换为二叉搜索树
#

# @lc code=start
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def sortedArrayToBST(self, nums: List[int]) -> TreeNode:
       
        def sortedArray(nums,root,rootindex,rindex,lindex):
            leftv=(rootindex+lindex)//2
            rightv=(rootindex+rindex+1)//2
            print(leftv,rightv,rootindex)
            if leftv!=rootindex:
                root.left=TreeNode(nums[leftv],None,None)
                x=lindex
                y=rootindex-1
                z=leftv
                sortedArray(nums,root.left,z,y,x)
            else:root.left=None
            if rightv!=rootindex:
                root.right=TreeNode(nums[rightv],None,None)
                l=rootindex+1
                m=rightv
                n=rindex 
                sortedArray(nums,root.right,m,n,l)
            else:root.right=None
        lens=len(nums)-1
        root = TreeNode(nums[lens//2],None,None)
        sortedArray(nums,root,lens//2,lens,0)  
        return root  
# @lc code=end

给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。

示例 1：

输入：root = [3,9,20,null,null,15,7]
输出：[[3],[9,20],[15,7]]

示例 2：

输入：root = [1]
输出：[[1]]

示例 3：

输入：root = []
输出：[]

层序遍历思路（队列）： 二叉树的节点加入队列， 出队的同时将其非空左右孩子依次入队，出队到队列为空即完成遍历。

#
# @lc app=leetcode.cn id=102 lang=python3
#
# [102] 二叉树的层序遍历
#思路就是将二叉树的节点加入队列，
# 出队的同时将其非空左右孩子依次入队，出队到队列为空即完成遍历。

# @lc code=start
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """
        if not root: return [] #注意特殊情况：树为空返回[]
        queue = [root]
        list1 = []
        while queue:
            list2 = []
            for i in range(len(queue)):
                a = queue.pop(0)#元素出队列
                if a.left:
                    queue.append(a.left)
                if a.right:
                    queue.append(a.right)
                list2.append(a.val)
            list1.append(list2)
        return list1
            
# @lc code=end

给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。

示例 1：

输入：n = 3
输出：5

示例 2：

输入：n = 1
输出：1

提示：

• 1 <= n <= 19

思路：动态规划方法：（需要仔细观察，动手绘画才能发现dp之间的规律）

dp[3]，就是 元素1为头结点搜索树的数量 + 元素2为头结点搜索树的数量 + 元素3为头结点搜索树的数量

元素1为头结点搜索树的数量 = 右子树有2个元素的搜索树数量 * 左子树有0个元素的搜索树数量

元素2为头结点搜索树的数量 = 右子树有1个元素的搜索树数量 * 左子树有1个元素的搜索树数量

元素3为头结点搜索树的数量 = 右子树有0个元素的搜索树数量 * 左子树有2个元素的搜索树数量

有2个元素的搜索树数量就是dp[2]。

有1个元素的搜索树数量就是dp[1]。

有0个元素的搜索树数量就是dp[0]。

所以dp[3] = dp[2] * dp[0] + dp[1] * dp[1] + dp[0] * dp[2]

1. 确定dp数组（dp table）以及下标的含义

dp[i] ： 1到i为节点组成的二叉搜索树的个数为dp[i]。

也可以理解是i的不同元素节点组成的二叉搜索树的个数为dp[i] ，都是一样的。

以下分析如果想不清楚，就来回想一下dp[i]的定义

2. 确定递推公式

在上面的分析中，其实已经看出其递推关系， dp[i] += dp[以j为头结点左子树节点数量] * dp[以j为头结点右子树节点数量]

j相当于是头结点的元素，从1遍历到i为止。

所以递推公式：dp[i] += dp[j – 1] * dp[i – j]; ，j-1 为j为头结点左子树节点数量，i-j 为以j为头结点右子树节点数量

3. dp数组如何初始化

初始化，只需要初始化dp[0]就可以了，推导的基础，都是dp[0]。

那么dp[0]应该是多少呢？

从定义上来讲，空节点也是一棵二叉树，也是一棵二叉搜索树，这是可以说得通的。

从递归公式上来讲，dp[以j为头结点左子树节点数量] * dp[以j为头结点右子树节点数量] 中以j为头结点左子树节点数量为0，也需要dp[以j为头结点左子树节点数量] = 1， 否则乘法的结果就都变成0了。

所以初始化dp[0] = 1

4. 确定遍历顺序

首先一定是遍历节点数，从递归公式：dp[i] += dp[j – 1] * dp[i – j]可以看出，节点数为i的状态是依靠 i之前节点数的状态。

那么遍历i里面每一个数作为头结点的状态，用j来遍历。

#
# @lc app=leetcode.cn id=96 lang=python3
#
# [96] 不同的二叉搜索树
#

# @lc code=start
class Solution:
    def numTrees(self, n: int) -> int:
        dp=[0]*(n+1)
        dp[0]=1
        for i in range(1,n+1):
            for j in range(1,i+1):
                dp[i] += dp[j - 1] * dp[i - j]
        return dp[n]
# @lc code=end

给定一个二叉树，找出其最大深度。

二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

说明: 叶子节点是指没有子节点的节点。

示例：
给定二叉树 [3,9,20,null,null,15,7]，

    3
   / \
  9  20
    /  \
   15   7

返回它的最大深度 3 。

代码：深度优先遍历：

# @lc app=leetcode.cn id=104 lang=python3
#
# [104] 二叉树的最大深度
#

# @lc code=start
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        def maxDepth(root):
            if root==None:
                return 0
            if root!=None:
               lf=maxDepth(root.left)
               ri=maxDepth(root.right)
               return max(lf,ri)+1
        return maxDepth(root)


# @lc code=end

给你一个二叉树的根节点 root ， 检查它是否轴对称。

示例 1：

输入：root = [1,2,2,3,4,4,3]
输出：true

示例 2：

输入：root = [1,2,2,null,3,null,3]
输出：false

代码：

# [101] 对称二叉树
#

# @lc code=start
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isSymmetric(self, root: TreeNode) -> bool:
        def isEqual(l,r):
            if l==None and r==None:
                return
            if l==None and r!=None:
                return False
            if l!=None and r==None:
                return False
            if l.val==r.val:
                if isEqual(l.left,r.right)==False or isEqual(l.right,r.left)==False:
                    return False
            else:
                return False
        return True if isEqual(root.left,root.right)==None else False
# @lc code=end

给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。

如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。

示例 1：

输入：p = [1,2,3], q = [1,2,3]
输出：true

# @lc app=leetcode.cn id=100 lang=python3
#
# [100] 相同的树
#

# @lc code=start
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
        def issame(p,q):
            if p==None and q==None:
                return
            if p==None and q!=None:
                return False
            if p!=None and q==None:
                return False
            if p.val==q.val:
                if issame(p.left,q.left)==False or issame(p.right,q.right)==False:
                    return False
            else:
                return False
        print(issame(p,q))
        return True if issame(p,q)==None else False
# @lc code=end

n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。

给你一个整数 n ，返回所有不同的 n皇后问题 的解决方案。

每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。

示例 1：

输入：n = 4
输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
解释：如上图所示，4 皇后问题存在两个不同的解法。

示例 2：

输入：n = 1
输出：[["Q"]]

回溯算法实现：

在如下树形结构中： 

可以看出，当递归到棋盘最底层（也就是叶子节点）的时候，就可以收集结果并返回了。

# @lc app=leetcode.cn id=51 lang=python3
#
# [51] N 皇后
#回溯算法 一行一行进行处理

# @lc code=start
class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        if not n: return []
        board = [['.'] * n for _ in range(n)]
        res = []
        def isVaild(board,row, col):
            #判断同一列是否冲突
            for i in range(len(board)):
                if board[i][col] == 'Q':
                    return False
            # 判断左上角是否冲突
            i = row -1
            j = col -1
            while i>=0 and j>=0:
                if board[i][j] == 'Q':
                    return False
                i -= 1
                j -= 1
            # 判断右上角是否冲突
            i = row - 1
            j = col + 1
            while i>=0 and j < len(board):
                if board[i][j] == 'Q':
                    return False
                i -= 1
                j += 1
            return True

        def backtracking(board, row, n):
            # 如果走到最后一行，说明已经找到一个解
            if row == n:
                temp_res = []
                for temp in board:
                    temp_str = "".join(temp)
                    temp_res.append(temp_str)
                res.append(temp_res)
            for col in range(n):
                if not isVaild(board, row, col):
                    continue
                board[row][col] = 'Q'
                backtracking(board, row+1, n)
                board[row][col] = '.'
        backtracking(board, 0, n)
        return res
# @lc code=end