判断是否是对称二叉树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def isSymmetric(self, root: TreeNode) -> bool:
    if not root:
        return False
    queue = [(root.left, root.right)]# 初始化队列
    '''
    1.空节点返回False
    2.根结点的左等于根结点的右
    3.如果有一个为空则返回False
    '''
    while queue:
        rt1, rt2 = queue.pop()
        if not rt1 and not rt2: #如果都为空则跳过
            continue
        if rt1.val != rt2.val:  #如果不相等 则返回False
            return False
        if not rt1.left and rt2.right:  # 如果左右有一个为空
            return False
        if not rt1.right and rt2.left: #同理
            return False
        queue.append((rt1.left, rt2.right)) #将左树的左节点跟右树的右节点入队
        queue.append((rt1.right, rt2.left)) #同理 将左树的右节点和右树的左节点入队
    return True

二叉树合并

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
def mergeTrees(self, root1: TreeNode, root2: TreeNode) -> TreeNode:
    if not root1 or not root2 :
        return  root1 if not root1 else root2  # 如果根结点有一个为空直接返回

    quese = [(root1, root2)]  #quese=[(1,2)]
    while quese:
        root1, root2 = quese.pop() # root1=1
        '''
       1.当树a为空 树b也不为空 树a=树a+树b
       2.当树a的左孩子为空,树b的左孩子不为空 树a=树b
        同理。。。
        '''
        if root1 and root2:
            root1.val += root2.val   #root1.val=1+2
        #右孩子 只判断树b的右孩子不为空的情况
        if root1.right and root2.right:
            quese.append((root1.right, root2.right))
        elif not root1.right and root2.right:
            root1.right = root2.right
        # elif root1.right and not root2.right:  # 不用判断
        #     root1.right = root2.right
       #左孩子 同理
        if root1.left and root2.left:
            quese.append((root1.left, root2.left))
        elif not root1.left and root2.left:
            root1.left = root2.left
    return root1

二叉树的反转(跟判断二叉树对称的方法一样)

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
 def invertTree(self, root: TreeNode) -> TreeNode:
     if not root:
         return None
     queue=[(root.left,root.right)] # 左右孩子入队
     while queue:
         rt1,rt2=queue.pop(0)  #左右孩子出队
         rt1.val,rt2.val = rt2.val,rt1.val # 交换节点的值
         if rt1.left or rt1.right:  # 左右孩子都为空则不入队
             queue.append((rt1.left,rt2.right))
         if rt2.left or rt2.right:
             queue.append((rt1.right,rt2.left)) #同理
     return root

总结

二叉树结构：把左右节点当作两个根结点的二叉树以此类推。很容易就想到递归。
这里用到迭代：把左右节点当作队列或者是栈，利用先进先出或先进后出的思想来完成相应的操作，以此类推每个子树都用这种思想，这样二叉树的一些操作就显得非常简单。

测试图片