leetcode226. 翻转二叉树
翻转一棵二叉树。
示例：
输入：
4
/ \
2 7
/ \ / \
1 3 6 9
输出：
4
/ \
7 2
/ \ / \
9 6 3 1
（1）递归写法：
关键点是对换当前根节点的左右节点和递归当前根节点的左右节点：
class Solution:
def invertTree(self, root: TreeNode) -> TreeNode:
if not root:
return
tmp=root.left
root.left=root.right
root.right=tmp
self.invertTree(root.left)
self.invertTree(root.right)
return root
（2）迭代写法
关键点：对换节点和不断引入右左节点，以及每次遍历一层，宽度优先遍历
class Solution:
def invertTree(self, root: TreeNode) -> TreeNode:
if not root:
return
d1=[root]
while d1:
for i in range(len(d1)):
t=d1.pop(0)
tmp=t.right
t.right=t.left
t.left=tmp
if t.left:
d1.append(t.left)
if t.right:
d1.append(t.right)
return root
leetcode617. 合并二叉树
给定两个二叉树，想象当你将它们中的一个覆盖到另一个上时，两个二叉树的一些节点便会重叠。
你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠，那么将他们的值相加作为节点合并后的新值，否则不为 NULL 的节点将直接作为新二叉树的节点。
示例 1:
输入:
Tree 1 Tree 2
1 2
/ \ / \
3 2 1 3
/ \ \
5 4 7
输出:
合并后的树:
3
/ \
4 5
/ \ \
5 4 7
注意: 合并必须从两个树的根节点开始。
(1)递归写法
关键点是比较节点和递归左右节点
代码如下：
class Solution:
def mergeTrees(self, t1: TreeNode, t2: TreeNode) -> TreeNode:
t=TreeNode()
if not t1 and not t2:
return
if not t1 or not t2:
if t1:
t=t1
if t2:
t=t2
if t1 and t2:
t.val=t1.val+t2.val
t.left=self.mergeTrees(t1.left,t2.left)
t.right=self.mergeTrees(t1.right,t2.right)
return t
（2）迭代写法
关键点：
1）一个队列的元素中包含左右树，先进行值加操作，确定都不为空添加，然后为空时如下：
2）判断左树为空，将右树值赋给左树
class Solution:
def mergeTrees(self, t1: TreeNode, t2: TreeNode) -> TreeNode:
if not (t1 and t2):
if not t1:
return t2
if not t2:
return t1
queue = [(t1,t2)]
while queue:
r1,r2 = queue.pop(0)
r1.val += r2.val
# 如果r1和r2的左子树都不为空，就放到队列中
# 如果r1的左子树为空，就把r2的左子树挂到r1的左子树上
if r1.left and r2.left:
queue.append((r1.left,r2.left))
elif not r1.left:
r1.left = r2.left
# 对于右子树也是一样的
if r1.right and r2.right:
queue.append((r1.right,r2.right))
elif not r1.right:
r1.right = r2.right
return t1
网友评论