作者： chenpaopao

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

给你一个整数数组 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