二叉树的深度、路径总和、将有序数组转换为二叉搜索树、二叉搜索树迭代器（2022/02/23）-阿里云开发者社区

104、二叉树的深度

难度：简单

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

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

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

示例：

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

9 20

15 7

返回它的最大深度 3 。

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:
        if root == None:
            return 0
        
        leftHeight = self.maxDepth(root.left)
        rightHeight = self.maxDepth(root.right)
        return max(leftHeight, rightHeight) + 1
    #  广度优先搜索
    def maxDepth(self, root: Optional[TreeNode]) -> int:  
        if not root:
            return 0
        queue = [root]
        res = 0
        while queue:
            size = len(queue)
            for _ in range(size):
                curr = queue.pop(0)
                if curr.left:
                    queue.append(curr.left)
                if curr.right:
                    queue.append(curr.right)
            res +=1
        return res

112、路径总和

难度：简单

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

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

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

输出：true 解释：等于目标和的根节点到叶节点路径如上图所示。

示例 2：输入：root = [1,2,3], targetSum

= 5 输出：false 解释：树中存在两条根节点到叶子节点的路径： (1 --> 2): 和为 3 (1 --> 3): 和为 4 不存在 sum = 5 的根节点到叶子节点的路径。

示例 3：输入：root = [], targetSum = 0 输出：false

解释：由于树是空的，所以不存在根节点到叶子节点的路径。

# 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:
        # 递归求解
        return self.sum(root, targetSum, 0)
    def sum(self, root:TreeNode, targetSum:int, currSum:int):
        if root == None:
            return False
        
        curSum += root.val
        if root.left == None and root.right == None:
            return currSum == targetSum
        else:
            return self.sum(root.left, targetSum, currSum) or self.sum(root.right, targetSum, currSum)
# 广度优先搜索进行遍历
    def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
        if not root:
            return False
        queue = [root]
        queue_val = [root.val]
        while queue:
            now = queue.pop(0)
            temp = queue_val.pop(0)
            if not now.left and not now.right:
                if temp == targetSum:
                    return True
                continue
            if now.left:
                queue.append(now.left)
                queue_val.append(now.left.val + temp )
            if now.right:
                queue.append(now.right)
                queue_val.append(now.right.val + temp)
        return False

111、二叉树的最小深度

难度：简单

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

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

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

示例 1:

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

输出：2

示例 2：

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

输出：5

# 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:
        if not root:
            return 0
        if not root.left and not root.right:
            return 1
        
        min_depth = 10**9
        if root.left:
            min_depth = min(self.minDepth(root.left), min_depth)
        if root.right:
            min_depth = min(self.minDepth(root.right), min_depth)
        return min_depth + 1
# 方法二：广度优先搜索
    import collections
    def minDepth(self, root: TreeNode) -> int:
        if not root:
            return 0
        que = collections.deque([(root,1)])
        while que:
            node, depth = que.popleft()
            if not node.left and not node.right:
                return depth
            
            if node.left:
                que.append((node.left, depth + 1))
            
            if node.right:
                que.append((node.right, depth + 1))
        return 0

108、将有序数组转换为二叉搜索树

难度：简单

给你一个整数数组 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] 都是高度平衡二叉搜索树。

提示：

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 sortedArrayToBST(self, nums: List[int]) -> TreeNode:
        def helper(left, right):
            if left > right:
                return None
            mid = (left + right) // 2
            root = TreeNode(nums[mid])
            root.left = helper(left, mid - 1)
            root.right = helper(mid + 1, right)
            return root
        return helper(0, len(nums) - 1)
    # 方法二：中序遍历，总是选择中间位置右边的数字作为根节点
    def sortedArrayToBST(self, nums: List[int]) -> TreeNode:
        def helper(left, right):
            if left >right:
                return None
            mid = (left + right + 1) //2
            root = TreeNode(nums[mid])
            root.left = helper(left, mid - 1)
            root.right = helper(mid + 1, right)
            return root
        return helper(0, len(nums) - 1)
    # 方法三：中序遍历，选择任意一个中间位置数字作为根节点
class Solution:
    def sortedArrayToBST(self, nums: List[int]) -> TreeNode:
        def helper(left, right):
            if left > right:
                return None
            # 选择任意一个中间位置数字作为根节点
            mid = (left + right + randint(0, 1)) // 2
            root = TreeNode(nums[mid])
            root.left = helper(left, mid - 1)
            root.right = helper(mid + 1, right)
            return root
        return helper(0, len(nums) - 1)

173、二叉搜索树迭代器

难度：中等

实现一个二叉搜索树迭代器类BSTIterator ，表示一个按中序遍历二叉搜索树（BST）的迭代器：

BSTIterator(TreeNode root) 初始化 BSTIterator 类的一个对象。BST 的根节点 root 会作为构造函数的一部分给出。指针应初始化为一个不存在于 BST 中的数字，且该数字小于 BST 中的任何元素。

boolean hasNext() 如果向指针右侧遍历存在数字，则返回 true ；否则返回 false 。

int next()将指针向右移动，然后返回指针处的数字。

注意，指针初始化为一个不存在于 BST 中的数字，所以对 next() 的首次调用将返回 BST 中的最小元素。

你可以假设 next() 调用总是有效的，也就是说，当调用 next() 时，BST 的中序遍历中至少存在一个下一个数字。

示例：

输入

[“BSTIterator”, “next”, “next”, “hasNext”, “next”, “hasNext”, “next”, “hasNext”, “next”, “hasNext”]

[[[7, 3, 15, null, null, 9, 20]], [], [], [], [], [], [], [], [], []]

输出

[null, 3, 7, true, 9, true, 15, true, 20, false]

解释

BSTIterator bSTIterator = new BSTIterator([7, 3, 15, null, null, 9, 20]);

bSTIterator.next(); // 返回 3

bSTIterator.next(); // 返回 7

bSTIterator.hasNext(); // 返回 True

bSTIterator.next(); // 返回 9

bSTIterator.hasNext(); // 返回 True

bSTIterator.next(); // 返回 15

bSTIterator.hasNext(); // 返回 True

bSTIterator.next(); // 返回 20

bSTIterator.hasNext(); // 返回 False

提示：

树中节点的数目在范围 [1, 105] 内

0 <= Node.val <= 106

最多调用 105 次 hasNext 和 next 操作

进阶：

你可以设计一个满足下述条件的解决方案吗？next() 和 hasNext() 操作均摊时间复杂度为 O(1) ，并使用 O(h) 内存。其中 h 是树的高度。

# 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 BSTIterator:
    def __init__(self, root: TreeNode):
        self.stack = []
        self.in_order(root)
    def next(self) -> int:
        node = self.stack.pop()
        if node.right:
            self.in_order(node.right)
        return node.val
    def in_order(self, node):
        while node:
            self.stack.append(node)
            node = node.left
    def hasNext(self) -> bool:
        return len(self.stack) != 0        
# Your BSTIterator object will be instantiated and called as such:
# obj = BSTIterator(root)
# param_1 = obj.next()
# param_2 = obj.hasNext()

二叉树的深度、路径总和、将有序数组转换为二叉搜索树、二叉搜索树迭代器（2022/02/23）

104、二叉树的深度

112、路径总和

111、二叉树的最小深度

108、将有序数组转换为二叉搜索树

173、二叉搜索树迭代器

热门文章

最新文章

相关电子书