参考文献 代码随想录
一、翻转二叉树
给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。
示例 1：
输入：root = [4,2,7,1,3,6,9] 输出：[4,7,2,9,6,3,1]
示例 2：
输入：root = [2,1,3] 输出：[2,3,1]
示例 3：
输入：root = [] 输出：[]
问题分析：左右节点交换，那么该如何去遍历这个树呢？可以使用前后序遍历，为什么不使用中序遍历呢？因为当你处理左节点时，那么处理后就变成了右节点，如果你在处理右节点，那不是不能到达翻转
递归：
# Definition for a binary tree node. # class TreeNode(object): # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution(object): def invertTree(self, root): """ :type root: TreeNode :rtype: TreeNode """ return self.dfs(root) def dfs(self, cur): if not cur: return cur.left, cur.right = cur.right, cur.left self.dfs(cur.left) self.dfs(cur.right) return cur
迭代：
# Definition for a binary tree node. # class TreeNode(object): # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution(object): def invertTree(self, root): """ :type root: TreeNode :rtype: TreeNode """ # 使用栈存储数据 from collections import deque stack = deque() if root: stack.append(root) while stack: node = stack.pop() # 为什么是中右左呢， 因为我们使用的是栈（先进后出） node.left, node.right = node.right, node.left # 中 if node.right: stack.append(node.right) # 右 if node.left: stack.append(node.left) # 左 return root
二、对称二叉树
给你一个二叉树的根节点 root ， 检查它是否轴对称。
示例 1：
输入：root = [1,2,2,3,4,4,3] 输出：true
示例 2：
输入：root = [1,2,2,null,3,null,3] 输出：false
问题分析：（同时循环跟节点的左右节点）如果对称，那么翻转后也是一样的，说明在数的两边最外的节点相等，而里面的节点应该相等，但是要判断它们是否为空，最后判断里面节点是否相等与外面节点是否相等的结果一样，就是为true，说明都满足。那么遍历方式是什么呢？答案是后序遍历，为什么呢，因为我们要判断里面节点和外面节点的结果是否都为True。
递归：
# Definition for a binary tree node. # class TreeNode(object): # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution(object): def isSymmetric(self, root): """ :type root: TreeNode :rtype: bool """ if not root: True return self.dfs(root.left, root.right) def dfs(self, left, right): if not left and right: return False elif left and not right: return False elif not left and not right: return True elif left.val != right.val: return False t = self.dfs(left.left, right.right) b = self.dfs(left.right, right.left) return True if t and b else False
迭代：
# Definition for a binary tree node. # class TreeNode(object): # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution(object): def isSymmetric(self, root): """ :type root: TreeNode :rtype: bool """ from collections import deque queen = deque() if not root: True queen.append(root.left) queen.append(root.right) while queen: tmp1 = queen.popleft() # left tmp2 = queen.popleft() # righ if not tmp1 and not tmp2: # 说明左右节点都为空， continue if not tmp1 or not tmp2 or tmp1.val != tmp2.val: # 一旦出现空或者是值不相等 return False queen.append(tmp1.left) queen.append(tmp2.right) queen.append(tmp1.right) queen.append(tmp2.left) return True
三、 二叉树的最大深度
给定一个二叉树 root ，返回其最大深度。
二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。
示例 1：
输入：root = [3,9,20,null,null,15,7] 输出：3
示例 2：
输入：root = [1,null,2] 输出：2
提示：
- 树中节点的数量在
[0, 104]区间内。 -100 <= Node.val <= 100
问题分析：最大深度，我们是不是可以判断每一层是否有值，简单所说，就是存储每一次的元素，然后在判断这个有多大（层次比遍历）
层次遍历：
# Definition for a binary tree node. # class TreeNode(object): # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution(object): def maxDepth(self, root): """ :type root: TreeNode :rtype: int """ from collections import deque queen = deque() ans = [] if root: queen.append(root) return self.bfs(queen, ans) def bfs(self, queen, ans): while queen: # 记录每层的个数 count = len(queen) tmp = [] # 存储每层的元素 while count: node = queen.popleft() tmp.append(node.val) if node.left: queen.append(node.left) if node.right: queen.append(node.right) count -= 1 ans.append(tmp) return len(ans)
递归：
# Definition for a binary tree node. # class TreeNode(object): # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution(object): def maxDepth(self, root): """ :type root: TreeNode :rtype: int """ if not root: return 0 def dfs(cur): if not cur: return 0 a = dfs(cur.left) b = dfs(cur.right) print(a, b) ans = 1 + max(a, b) return ans return dfs(root)
四、二叉树的最小深度
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明：叶子节点是指没有子节点的节点。
示例 1：
输入：root = [3,9,20,null,null,15,7] 输出：2
示例 2：
输入：root = [2,null,3,null,4,null,5,null,6] 输出：5
迭代：
# Definition for a binary tree node. # class TreeNode(object): # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution(object): def minDepth(self, root): """ :type root: TreeNode :rtype: int """ from collections import deque queen = deque() ans = [] if root: queen.append(root) deep = 0 return self.bfs(queen, deep) def bfs(self, queen, deep): while queen: # 记录每层的个数 deep += 1 count = len(queen) while count: node = queen.popleft() if not node.left and not node.right: return deep if node.left: queen.append(node.left) if node.right: queen.append(node.right) count -= 1 return deep
递归：
# Definition for a binary tree node. # class TreeNode(object): # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution(object): def minDepth(self, root): """ :type root: TreeNode :rtype: int """ return self.getDepth(root) def getDepth(self, node): if node is None: return 0 leftDepth = self.getDepth(node.left) # 左 rightDepth = self.getDepth(node.right) # 右 # 当一个左子树为空，右不为空，这时并不是最低点 if node.left is None and node.right is not None: return 1 + rightDepth # 当一个右子树为空，左不为空，这时并不是最低点 if node.left is not None and node.right is None: return 1 + leftDepth result = 1 + min(leftDepth, rightDepth) return result
