欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

深度优先搜索和广度优先搜索

程序员文章站 2022-05-22 20:22:42
...

617.合并二叉树

给定两个二叉树,想象当你将它们中的一个覆盖到另一个上时,两个二叉树的一些节点便会重叠。

你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠,那么将他们的值相加作为节点合并后的新值,否则不为 NULL 的节点将直接作为新二叉树的节点。

思路: 每次要存两个树节点的元祖共同遍历,直接在左树上进行操作,在循环中先将左树加上右树值,再对两个节点的左右子树判定,都为非空则入队列,否则直接赋值左树的左右子树为另一非空值。
bfs:

# 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 mergeTrees(self, root1: TreeNode, root2: TreeNode) -> TreeNode:
        q = collections.deque()
        if not root1 or not root2:
            return root1 if root1 else root2
        q.append((root1, root2))
        while q:
            r1, r2 = q.popleft()
            r1.val += r2.val
            if r1.left and r2.left:
                q.append((r1.left, r2.left))
            elif not r1.left:
                r1.left = r2.left
            if r1.right and r2.right:
                q.append((r1.right, r2.right))
            elif not r1.right:
                r1.right = r2.right
        return root1

dfs:
思路: 在左树上操作,dfs返回树节点,每次先判断是否都为空,有空直接返回,否则左树加上右树,左树左子树和右子树分别递归,最后返回左子树

# 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 mergeTrees(self, root1: TreeNode, root2: TreeNode) -> TreeNode:
        def dfs(l, r):
            if not l or not r:
                return l if l else r 
            l.val += r.val
            l.left = dfs(l.left, r.left)
            l.right = dfs(l.right, r.right)
            return l
        return dfs(root1, root2)
                
相关标签: 算法