深度优先搜索和广度优先搜索
程序员文章站
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)