leetcode刷题之广度搜索

作者: sk邵楷 | 来源:发表于2022-06-30 22:39 被阅读0次

1, 相同的树—— 0100 广度搜索深度搜索
给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。
如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。

import collections

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

#深度搜索
class Solution:
    def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
        if not p and not q:
            return True
        elif not p or not q:
            return False
        elif p.val != q.val:
            return False
        else:
            return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)

#广度搜索
class Solution2:
    def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
        if not p and not q:
            return True
        if not p or not q:
            return False

        queue1 = collections.deque([p])
        queue2 = collections.deque([q])

        while queue1 and queue2:
            node1 = queue1.popleft()
            node2 = queue2.popleft()
            if node1.val != node2.val:
                return False

            left1, right1 = node1.left, node1.right
            left2, right2 = node2.left, node2.right

            if (not left1) ^ (not left2):
                return False
            if (not right1) ^ (not right2):
                return False

            if left1:
                queue1.append(left1)
            if right1:
                queue1.append(right1)
            if left2:
                queue2.append(left2)
            if right2:
                queue2.append(right2)

        return not queue1 and not queue2
p = TreeNode(1)
q = TreeNode(1)
b = TreeNode(2)
c = TreeNode(3)
d = TreeNode(2)
e = TreeNode(3)
p.left = b
p.right = c
q.left = d
q.right = e
S = Solution()
print(S.isSameTree(p, q))
S2 = Solution2()
print(S2.isSameTree(p, q))

2, 对称二叉树—— 101 递归迭代
给你一个二叉树的根节点 root ，检查它是否轴对称。
输入：root = [1,2,2,3,4,4,3]
输出：true

from typing import  Optional
import collections

# 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 isSymmetric(self, root: Optional[TreeNode]) -> bool:
        if not root.left and not root.right:
            return True
        if not root.left or not root.right:
            return False

        p, q = root.left, root.right

        def dfs(p, q):
            if not p and not q:
                return True
            if (not p or not q) or p.val != q.val:
                return False

            return dfs(p.left, q.right) and dfs(p.right, q.left)

        return dfs(p, q)

#改造为迭代
class Solution2:
    def isSymmetric(self, root: Optional[TreeNode]) -> bool:
        if not root.left and not root.right:
            return True
        if not root.left or not root.right:
            return False
        p, q = root.left, root.right
        def check(p, q):
            queue1 = collections.deque()
            queue1.append(p)
            queue1.append(q)

            while queue1:
                node1 = queue1.popleft()
                node2 = queue1.popleft()

                if not node1 and not node2:
                    continue
                if (not node1 or not node2) or node1.val != node2.val:
                    return False

                queue1.append(node1.left)
                queue1.append(node2.right)
                queue1.append(node1.right)
                queue1.append(node2.left)
            return True

        return check(p, q)
root = TreeNode(1)
a1 = TreeNode(2)
a2 = TreeNode(2)
a3 = TreeNode(3)
a4 = TreeNode(4)
a5 = TreeNode(4)
a6 = TreeNode(3)
root.left = a1
root.right = a2
a1.left = a3
a1.right = a4
a2.left = a5
a2.right = a6
S = Solution()
print(S.isSymmetric(root))
S2 = Solution2()
print(S2.isSymmetric(root))

3, 二叉树的层序遍历—— 102 广度搜索
给你二叉树的根节点 root ，返回其节点值的层序遍历。（即逐层地，从左到右访问所有节点）。

from typing import List
from collections import deque

# 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]]:
        if not root:
            return []

        res = []
        que = deque()
        que.append(root)

        while que:
            size = len(que)
            level = []
            for _ in range(size):
                node = que.popleft()
                level.append(node.val)
                if node.left:
                    que.append(node.left)
                if node.right:
                    que.append(node.right)

            res.append(level)
        return res

root = TreeNode(3)
a1 = TreeNode(9)
a2 = TreeNode(20)
a3 = TreeNode(15)
a4 = TreeNode(7)
root.left = a1
root.right = a2
a2.left = a3
a2.right = a4
S = Solution()
print(S.levelOrder(root))

4, 二叉树的最大深度—— 104 广度搜索
给定一个二叉树，找出其最大深度。

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

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

示例：
给定二叉树 [3,9,20,null,null,15,7]，返回它的最大深度 3 。

from typing import List
from collections import deque
from typing import  Optional

# 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:

        if not root:
            return 0

        que = deque()

        high = 0

        que.append(root)

        while que:
            size = len(que)
            for _ in range(size):
                node = que.popleft()
                if node.left:
                    que.append(node.left)
                if node.right:
                    que.append(node.right)

            high += 1

        return high


root = TreeNode(3)
a1 = TreeNode(9)
a2 = TreeNode(20)
a3 = TreeNode(15)
a4 = TreeNode(7)
root.left = a1
root.right = a2
a2.left = a3
a2.right = a4
S = Solution()
print(S.maxDepth(root))

5, 二叉树的层序遍历 II —— 107 广度遍历
给你二叉树的根节点 root ，返回其节点值自底向上的层序遍历。（即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）
输入：root = [3,9,20,null,null,15,7]
输出：[[15,7],[9,20],[3]]

from typing import List
from collections import deque

# 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 []

        res = list()
        que = deque()
        que.append(root)

        while que:
            size = len(que)
            level = list()
            for _ in range(size):
                node = que.popleft()
                level.append(node.val)
                if node.left:
                    que.append(node.left)
                if node.right:
                    que.append(node.right)

            res.append(level)
        # return res[::-1]
        res.reverse()
        return res


root = TreeNode(3)
a1 = TreeNode(9)
a2 = TreeNode(20)
a3 = TreeNode(15)
a4 = TreeNode(7)
root.left = a1
root.right = a2
a2.left = a3
a2.right = a4
S = Solution()
print(S.levelOrderBottom(root))

6, 二叉树的最小深度—— 111 广度遍历
给定一个二叉树，找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明：叶子节点是指没有子节点的节点。
示例 1：
输入：root = [3,9,20,null,null,15,7]
输出：2
示例 2：
输入：root = [2,null,3,null,4,null,5,null,6]
输出：5

from typing import List
from collections import deque

# 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

        que = deque()
        que.append(root)

        res = 0

        while que:
            size = len(que)
            res = res + 1

            for _ in range(size):
                node = que.popleft()
                if not node.left and not node.right:
                    return res

                if node.left:
                    que.append(node.left)

                if node.right:
                    que.append(node.right)

root = TreeNode(3)
a1 = TreeNode(9)
a2 = TreeNode(20)
a3 = TreeNode(15)
a4 = TreeNode(7)
root.left = a1
root.right = a2
a2.left = a3
a2.right = a4
S = Solution()
print(S.minDepth(root))

7, 路径总和——112 递归广度搜索
给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和 targetSum 。如果存在，返回 true ；否则，返回 false 。
输入：root = [1,2,3], targetSum = 5
输出：false
输入：root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
输出：true

from typing import List
from collections import deque
from typing import  Optional

# 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:

        if not root:
            return False

        if not root.left and not root.right:
            if targetSum == root.val:
                return True
            else:
                return False

        return self.hasPathSum(root.left, targetSum-root.val) or self.hasPathSum(root.right, targetSum-root.val)

    # 广度搜索
    def hasPathSum2(self, root: Optional[TreeNode], targetSum: int) -> bool:

        if not root:
            return False

        que = deque()
        que.append(root)
        que2 = deque()
        que2.append(root.val)

        while que:
            size = len(que)
            for _ in range(size):
                node = que.popleft()
                sum  = que2.popleft()

                if not node.left and not node.right:
                    if sum == targetSum:
                        return True

                if node.left:
                    que.append(node.left)
                    que2.append(sum+node.left.val)

                if node.right:
                    que.append(node.right)
                    que2.append(sum + node.right.val)
        return False



root = TreeNode(1)
a1 = TreeNode(2)
a2 = TreeNode(3)
root.left = a1
root.right = a2

S = Solution()
print(S.hasPathSum(root, 3))

S = Solution()
print(S.hasPathSum2(root, 5))

leetcode刷题之广度搜索

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读