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:二刷再看其他实现方法。