leetcode基础编程:树

举报
irrational 发表于 2022/02/24 22:32:15 2022/02/24
【摘要】 88. 二叉树的最大深度 难度:简单 给定一个二叉树,找出其最大深度。 二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。 说明: 叶子节点是指没有子节点的节点。 示例: 给定二叉树 [3...

88. 二叉树的最大深度

难度:简单

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

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

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

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

3

  
 

/ \
9 20
   / \
15 7
返回它的最大深度 3 。

方法一

# 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 dfs(self,root:Optional[TreeNode],temp:int,ans:int):
        if not root:
            self.ans=max(self.ans,temp)
            return
        temp=temp+1
        self.dfs(root.left,temp,self.ans)
        self.dfs(root.right,temp,self.ans)
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        self.ans=0
        temp=0
        self.dfs(root,temp,self.ans)
        return self.ans

  
 

方法二

# 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 dfs(self,root:Optional[TreeNode]):
        if not root:
            return 0
        left=self.dfs(root.left)
        right=self.dfs(root.right)
        ans = max(left,right)+1
        return ans
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        
        ans=self.dfs(root)
        return ans

  
 

方法三

# 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:
        ans=0
        q=[]
        q.append(root)
        while len(q) and q[0]:
            ans +=1
            size=len(q)
            for i in range(len(q)):
                cur=q.pop(0)
                if cur.left:
                    q.append(cur.left)
                if cur.right:
                    q.append(cur.right)
        return ans

  
 

\92. 将有序数组转换为二叉搜索树

难度:简单

收藏

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

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

示例 1:

img

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

  
 

示例 2:

img

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

  
 

提示:

  • 1 <= nums.length <= 104
  • -104 <= nums[i] <= 104
  • nums严格递增 顺序排列
# 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 buildBST(self,nums:List[int],lo:int,hi:int)-> TreeNode:
        if lo > hi:
            return None
        mid = int(lo+(hi-lo)/2)
        root = TreeNode(nums[mid])
        root.left= self.buildBST(nums,lo,mid-1)
        root.right = self.buildBST(nums,mid+1,hi)
        return root
    def sortedArrayToBST(self, nums: List[int]) -> TreeNode:
        lo,hi=0,len(nums)-1
        ans=self.buildBST(nums,lo,hi)
        return ans

  
 

文章来源: blog.csdn.net,作者:irrationality,版权归原作者所有,如需转载,请联系作者。

原文链接:blog.csdn.net/weixin_54227557/article/details/123099924

【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。