代码随想录算法训练营第十五天|102. 二叉树的层序遍历、226. 翻转二叉树、101. 对称二叉树

【参考链接】

102. 二叉树的层序遍历

 【注意】

1.队列先进先出，符合一层一层遍历的逻辑，而用栈先进后出适合模拟深度优先遍历也就是递归的逻辑。而这种层序遍历方式就是图论中的广度优先遍历，只不过我们应用在二叉树上。

2.遍历的时候要记录队列的大小。就可以知道哪些元素是第几层的。

3.记得首先要判断root不为空。  

4.当队列不为空，就一直去遍历。

【代码】

 1 # Definition for a binary tree node.
 2 # class TreeNode(object):
 3 #     def __init__(self, val=0, left=None, right=None):
 4 #         self.val = val
 5 #         self.left = left
 6 #         self.right = right
 7 class Solution(object):
 8     def levelOrder(self, root):
 9         """
10         :type root: TreeNode
11         :rtype: List[List[int]]
12         """
13         #方法1.利用长度法
14         #root若为空，直接返回空列表
15         if not root:
16             return []
17         queue = collections.deque([root]) #队列存储遍历的每一层
18         result = [] #返回一个二维数组
19         while queue:
20             #队列不为空，就一直遍历下去
21             level = []
22             for _ in range(len(queue)):#当前队列长度，记录每一层所含节点个数
23                 cur = queue.popleft()
24                 level.append(cur.val)
25                 if cur.left:
26                     queue.append(cur.left)
27                 if cur.right:
28                     queue.append(cur.right)
29             result.append(level) #将遍历完的每一层结果追加到result中
30         return result
31 
32         #方法2.递归法
33 
34         levels = []
35         self.helper(root,0,levels)
36         return levels
37         
38     def helper(self, node, level, levels):
39         if not node:
40              return
41         if len(levels) == level:
42             levels.append([])
43         levels[level].append(node.val)
44         self.helper(node.left, level + 1, levels)
45         self.helper(node.right, level + 1, levels)

ps：递归法没有理解透，二刷的时候记得看。

226. 翻转二叉树

【注意】

1.两两交换的是指针。

2.利用前序和后序。

3.也可以使用层序遍历。

【代码】

 1 # Definition for a binary tree node.
 2 # class TreeNode(object):
 3 #     def __init__(self, val=0, left=None, right=None):
 4 #         self.val = val
 5 #         self.left = left
 6 #         self.right = right
 7 class Solution(object):
 8     def invertTree(self, root):
 9         """
10         :type root: TreeNode
11         :rtype: TreeNode
12         """
13         #1.递归法：前序遍历
14         if not root:#为空。返回None
15             return None
16         #交换左右节点
17         root.left, root.right = root.right, root.left
18         #遍历
19         self.invertTree(root.left)
20         self.invertTree(root.right)
21 
22         return root
23 
24         #2.迭代法：前序遍历
25         if not root:
26             return None
27         stack = [root] #栈
28         while stack:
29             node = stack.pop()
30             node.left, node.right = node.right, node.left
31             if node.left:
32                 stack.append(node.left)
33             if node.right:
34                 stack.append(node.right)
35 
36         return root

ps：之后再看其他实现方法。

101. 对称二叉树

【注意】

1.二叉树最终考察的是我们如何遍历。

2.收集左右孩子节点的信息返回给根节点，所以使用后序。

3.判断左右子树是否可以反转。

【代码】

 1 # Definition for a binary tree node.
 2 # class TreeNode(object):
 3 #     def __init__(self, val=0, left=None, right=None):
 4 #         self.val = val
 5 #         self.left = left
 6 #         self.right = right
 7 class Solution(object):
 8     def isSymmetric(self, root):
 9         """
10         :type root: TreeNode
11         :rtype: bool
12         """
13         #1.递归法
14         #终止条件，root为空时也是对称的，所以返回True
15         if not root:
16             return True
17         return self.compare(root.left,root.right)
18 
19     def compare(self, left, right):
20         #首先排除空节点的情况
21         if left == None and right != None: return flase
22         elif left != None and right == None: return False
23         elif left == None and right == None: return True
24         #排除了空节点，再排除数值不相同的情况
25         elif left.val != right.val: return False
26         
27         #此时就是：左右节点都不为空，且数值相同的情况
28         #此时才做递归，做下一层的判断
29         outside = self.compare(left.left, right.right) #左子树：左、 右子树：右
30         inside = self.compare(left.right, right.left) #左子树：右、 右子树：左
31         isSame = outside and inside #左子树：中、 右子树：中 （逻辑处理）
32         
33         return isSame

ps:二刷再看其他实现方法。