chenpaopao

给定一个 N 叉树，返回其节点值的层序遍历。（即从左到右，逐层遍历）。

树的序列化输入是用层序遍历，每组子节点都由 null 值分隔（参见示例）。

示例 1：

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

示例 2：

# [429] N 叉树的层序遍历
#

# @lc code=start
"""
# Definition for a Node.
class Node:
    def __init__(self, val=None, children=None):
        self.val = val
        self.children = children
"""

class Solution:
    def levelOrder(self, root: 'Node') -> List[List[int]]:
        if not root: return [] #注意特殊情况：树为空返回[]
        queue = [root]
        list1 = []
        while queue:
            list2 = []
            lens=len(queue)
            for i in range(lens):
                a = queue.pop(0)#元素出队列
                for i in range(len(a.children)):
                    queue.append(a.children[i])
                     
                list2.append(a.val)
            list1.append(list2)
        return list1

        
# @lc code=end

给定一个非空二叉树的根节点 root , 以数组的形式返回每一层节点的平均值。与实际答案相差 10-5 以内的答案可以被接受。

# @lc app=leetcode.cn id=637 lang=python3
#
# [637] 二叉树的层平均值
#

# @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 averageOfLevels(self, root: Optional[TreeNode]) -> List[float]:
        if not root: return [] #注意特殊情况：树为空返回[]
        queue = [root]
        list1 = []
        while queue:
            list2 = 0
            lens=len(queue)
            for i in range(lens):
                a = queue.pop(0)#元素出队列
                if a.left :
                    queue.append(a.left)    
                if a.right:
                    queue.append(a.right)        
                list2=list2+a.val
            
            list1.append(list2/lens)
        return list1
# @lc code=end

给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。

示例 1:

输入: [1,2,3,null,5,null,4]
输出: [1,3,4]

示例 2:

输入: [1,null,3]
输出: [1,3]

示例 3:

输入: []
输出: []

# @lc app=leetcode.cn id=199 lang=python3
#
# [199] 二叉树的右视图
#

# @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 rightSideView(self, root: TreeNode) -> 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[-1])
        return list1
# @lc code=end

给你二叉树的根节点 root ，返回其节点值 自底向上的层序遍历 。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）

示例 1：

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

示例 2：

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

# @lc app=leetcode.cn id=107 lang=python3
#
# [107] 二叉树的层序遍历 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 levelOrderBottom(self, root: TreeNode) -> 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)
        list1.reverse()
        return list1
# @lc code=end

# @lc app=leetcode.cn id=145 lang=python3
#
# [145] 二叉树的后序遍历
#

# @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 postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        result = []
        
        def traversal(root: TreeNode):
            if root == None:
                return
            
            traversal(root.left)    # 左
            traversal(root.right)   # 右
            result.append(root.val) # 后序

        traversal(root)
        return result
# @lc code=end

# @lc app=leetcode.cn id=144 lang=python3
#
# [144] 二叉树的前序遍历
#

# @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 preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        # 保存结果
        result = []
        
        def traversal(root: TreeNode):
            if root == None:
                return
            result.append(root.val) # 前序
            traversal(root.left)    # 左
            traversal(root.right)   # 右

        traversal(root)
        return result
# @lc code=end

给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。

有效 二叉搜索树定义如下：

• 节点的左子树只包含 小于 当前节点的数。
• 节点的右子树只包含 大于 当前节点的数。
• 所有左子树和右子树自身必须也是二叉搜索树。

# @lc app=leetcode.cn id=98 lang=python3
#
# [98] 验证二叉搜索树
#

# @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 isValidBST(self, root: TreeNode) -> bool:
        nums=[]
        def isValid(root):

            if root == None:
                return 
            
            isValid(root.left)
            nums.append(root.val)    
            isValid(root.right)
        isValid(root)
        for i in range(len(nums)-1):
            j=i+1
            if nums[i]>=nums[j]:
                return False
            
        return True


                
# @lc code=end

# @lc app=leetcode.cn id=98 lang=python3
#
# [98] 验证二叉搜索树
#

# @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 isValidBST(self, root: TreeNode) -> bool:
        nums=[-2**31-1]
        def isValid(root):
            if root == None:
                return True
            if isValid(root.left)==False:
                return False
            if root.val > nums[0]:
                nums[0]= root.val
            else: 
                return False
            if isValid(root.right)==False:
                return False
        return isValid(root) if isValid(root)==False else True



                
# @lc code=end

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