每日归档： 2022年1月29日

给你二叉树的根节点 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