226.翻转二叉树
给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。
使用递归解决。
- 确定函数参数和返回值
函数参数为当前节点cur。无返回值。
def dd(cur):
- 确定终止条件。当前节点为空则终止。
if not cur: return
- 单层逻辑
反转当前节点的左右，然后递归调用cur.left, cur.right
def dd(cur): if not cur: return cur.left, cur.right = cur.right, cur.left dd(cur.left) dd(cur.right)
完整代码如下：
class Solution: def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]: def dd(cur): if not cur: return cur.left, cur.right = cur.right, cur.left dd(cur.left) dd(cur.right) dd(root) return root
101.对称二叉树
给你一个二叉树的根节点 root ， 检查它是否轴对称。
这题用层序遍历很好做，只要判断每层是不是对称的就好了（空的节点添加一个特殊值方便判断对称）。
# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution: def isSymmetric(self, root: Optional[TreeNode]) -> bool: def symmetric_list(lst): length = len(lst) i = 0 j = length-1 while i < j: if lst[i] != lst[j]: return False i += 1 j -= 1 return True res = [] if not root: return res queue = deque() queue.append(root) while len(queue) > 0: next_list = [] length = len(queue) for i in range(length): node = queue.popleft() if node.left: queue.append(node.left) next_list.append(node.left.val) else: next_list.append(-9999) if node.right: queue.append(node.right) next_list.append(node.right.val) else: next_list.append(-9999) if not symmetric_list(next_list): return False return True
递归方式有点绕，因为要判断的是轴对称。
- 函数参数和返回值。
参数是左子节点和右子节点。返回值是 bool值，表示是否当前节点是否轴对称。
def compare(left, right):
- 终止条件。
左右节点全为空或某个为空时，则可以判断出当前节点的左右是否是对称的了。
if not left and not right: return True elif not left or not right: return False
- 单层逻辑
return left.val == right.val and \ compare(left.left, right.right) and compare(left.right, right.left)
104.二叉树的最大深度
给定一个二叉树 root ，返回其最大深度。
层序遍历非常直接，遍历的层数就是深度。
class Solution: def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]: res = [] if not root: return res queue = deque() queue.append(root) while len(queue) > 0: sub_list = [] length = len(queue) # 注意 for i in range(length): node = queue.popleft() sub_list.append(node.val) if node.left: queue.append(node.left) if node.right: queue.append(node.right) res.append(sub_list) return res def maxDepth(self, root: Optional[TreeNode]) -> int: res = self.levelOrder(root) return len(res)
递归更简单：
- 函数参数和返回值。
参数为当前节点node。返回值为int值，表示节点的深度。 - 终止条件
节点为空时，返回0. - 单层逻辑
max(左节点深度,右节点深度) +1
class Solution: def maxDepth(self, root: Optional[TreeNode]) -> int: def depth(node): if not node: return 0 leftDepth = depth(node.left) rightDepth = depth(node.right) return max(leftDepth, rightDepth)+1 return depth(root)
- 二叉树节点的深度：指从根节点到该节点的最长简单路径边的条数。
- 二叉树节点的高度：指从该节点到叶子节点的最长简单路径边的条数。
本题可以使用前序遍历（中左右），也可以使用后序遍历（左右中），使用前序求的就是深度，使用后序求的是高度。
- 而根节点的高度就是二叉树的最大深度，所以本题中我们通过后序求的根节点高度来求的二叉树最大深度。
111.二叉树的最小深度
给定一个二叉树，找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
这题层序遍历还是很简单，因为每遍历一层就对应深度+1。如果找到了叶子节点就可以终止遍历返回当前深度了。
class Solution: def minDepth(self, root: Optional[TreeNode]) -> int: if not root: return 0 queue = deque() queue.append(root) depth = 0 while queue: depth += 1 length = len(queue) for i in range(length): node = queue.popleft() if all([not node.left, not node.right]): return depth for nextnode in [node.left, node.right]: if nextnode: queue.append(nextnode) return depth
递归方式。
递归方式和104求最大深度差很多。最小深度必须是根节点到叶子节点的长度，如果左子树为空，右子树不为空，则只能通过右子树到达叶子节点(1+rightDepth)。
递归公式：
- 函数参数和返回值。
参数为当前节点node。返回值为int值，表示节点的深度。 - 终止条件
节点为空时，返回0. - 单层逻辑
- 如果只有右子树，返回 1+rightDepth
如果只有左子树，返回 1+leftDepth
否则，返回 min(左节点深度,右节点深度) +1
class Solution: def minDepth(self, root: Optional[TreeNode]) -> int: def getDepth(node: Optional[TreeNode]) -> int: if not node : return 0 leftDepth = getDepth(node.left) rightDepth = getDepth(node.right) if not node.left and node.right : return 1+ rightDepth if not node.right and node.left: return 1+ leftDepth return 1 + min(leftDepth, rightDepth) return getDepth(root)
222.完全二叉树的节点个数
给你一棵 完全二叉树 的根节点 root ，求出该树的节点个数。
遍历一次就知道节点个数了。
但是这样就没有用到完全二叉树的性质。
完全二叉树只有两种情况，情况一：就是满二叉树，情况二：最后一层叶子节点没有满。
对于情况一，可以直接用 2^树深度 - 1 来计算，注意这里根节点深度为1。
对于情况二，分别递归左孩子，和右孩子，递归到某一深度一定会有左孩子或者右孩子为满二叉树，然后依然可以按照情况1来计算。
递归公式：
- 函数参数和返回值。
参数是当前节点。返回值是当前节点为根节点的树的节点个数。 - 终止条件
如果节点为None，返回0。 - 单层逻辑
判断当前节点是不是满二叉树，是满二叉树则直接用公式2^树深度 - 1返回节点数。否则递归处理左右子树，返回左子树节点数 + 右子树节点数 + 1。
class Solution: def countNodes(self, root: Optional[TreeNode]) -> int: if not root: return 0 # 判断当前节点是不是满二叉树 leftHeight, rightHeight = 0, 0 left, right = root.left, root.right while left: left = left.left leftHeight += 1 while right: right = right.right rightHeight += 1 # 是满二叉树，则用公式计算 if leftHeight == rightHeight: return (2 << leftHeight) -1 # 否则递归处理left, right return self.countNodes(root.left) + self.countNodes(root.right) + 1
110.平衡二叉树
给定一个二叉树，判断它是否是高度平衡的二叉树。
一个二叉树每个节点的左右两个子树的高度差的绝对值不超过 1 。
- 二叉树节点的深度：指从根节点到该节点的最长简单路径边的条数。
- 二叉树节点的高度：指从该节点到叶子节点的最长简单路径边的条数。
LeetCode上的不是按照路径数，而是按照节点数计算。
求深度可以从上到下去查 所以需要前序遍历（中左右），而高度只能从下到上去查，所以只能后序遍历（左右中）。
递归公式
- 函数参数和返回值
参数为当前节点，返回值为节点的高度。返回值为-1时表示不是平衡二叉树。 - 终止条件
节点为None，返回0。 - 单层逻辑
- 求左子树高度，如果为-1，则已经不平衡了，返回-1.
求右子树高度，如果为-1，则已经不平衡了，返回-1.
如果左右子树高度差>1，不平衡，返回-1.
否则返回当前节点的高度，1 + max(leftDepth, rightDepth)
class Solution: def isBalanced(self, root: Optional[TreeNode]) -> bool: def getHeight(node): if not node: return 0 leftDepth = getHeight(node.left) if leftDepth == -1: return -1 rightDepth = getHeight(node.right) if rightDepth == -1: return -1 if abs(leftDepth - rightDepth) > 1: return -1 else: return 1 + max(leftDepth, rightDepth) return not getHeight(root) == -1
257.二叉树的所有路径
按 任意顺序 ，返回所有从根节点到叶子节点的路径。
递归+回溯。
递归公式
- 参数和返回值
参数是当前节点、路径、（存放结果的数组）。返回值无。 - 终止条件
到达叶子节点。 - 单层逻辑
添加当前节点，递归（+回溯）遍历左子树和右子树。
class Solution: def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]: def traversal(cur, path, result): path.append(cur.val) # 终止条件：到达叶子节点了 if not any([cur.left, cur.right]): sPath = "" for n in path: sPath += str(n) sPath += "->" sPath = sPath[:-2] result.append(sPath) return # 左子树 if cur.left: traversal(cur.left, path, result) path.pop() # 回溯 # 右子树 if cur.right: traversal(cur.right, path, result) path.pop() result = [] path = [] if not root: return result traversal(root, path, result) return result
404.左叶子之和
给定二叉树的根节点 root ，返回所有左叶子之和。
左叶子：是父节点的左节点，并且是叶子节点。
递归公式：
- 函数参数和返回值
参数是当前节点，返回值是当前节点的左叶子之和。 - 终止条件
当前节点为None，返回0. - 单层逻辑
如果当前节点是左叶子，则要加入当前节点的值。然后加上左子树的左叶子和，右子树的左叶子和。
class Solution: def sumOfLeftLeaves(self, root: Optional[TreeNode]) -> int: def getLeft(node): if not node: return 0 leftValue = getLeft(node.left) rightValue = getLeft(node.right) midValue = 0 # 左叶子： # 它是父节点的左节点，同时它是叶子节点 if node.left and node.left.left == None and node.left.right ==None: midValue = node.left.val return midValue + leftValue + rightValue return getLeft(root)
513.找树左下角的值
给定一个二叉树的 根节点 root，请找出该二叉树的 最底层 最左边 节点的值。
层序遍历比较简单，遍历完然后获取最后一层的第一个节点。
# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution: def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]: res = [] if not root: return res queue = deque() queue.append(root) while queue: sub_list = [] length = len(queue) for i in range(length): node = queue.popleft() sub_list.append(node.val) for nextnode in [node.left, node.right]: if nextnode: queue.append(nextnode) res.append(sub_list) return res def findBottomLeftValue(self, root: Optional[TreeNode]) -> int: return self.levelOrder(root)[-1][0]
递归方式。
递归找最底层最左的节点，需要知道层数。
递归公式：
- 函数参数和返回值。
参数是当前节点和当前层数。 - 终止条件
到达叶子节点。 - 单层逻辑
递归处理左子树和右子树，深度+1.
class Solution: def findBottomLeftValue(self, root: Optional[TreeNode]) -> int: maxDepth = -11111 # 最大深度 maxLeftValue = 0 # 最深层 最左的节点值 def traversal(root, depth): nonlocal maxDepth, maxLeftValue # 终止条件： 到达叶子 if not root.left and not root.right: # 深度是最深的，更新答案 if depth > maxDepth: maxDepth = depth maxLeftValue = root.val return # 递归处理左右 if root.left: traversal(root.left, depth+1) # 隐藏回溯 if root.right: traversal(root.right, depth+1) return traversal(root,0) return maxLeftValue
112.路径总和
给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。如果存在，返回 true ；否则，返回 false 。
递归公式：
- 函数参数和返回值
参数：当前节点root，目标和targetSum。
返回值：bool值，表示是否满足题目要求。 - 终止条件：
当前节点为None，返回False - 单层逻辑：
如果是叶子节点，判断当前值和目标值是否相等。
否则对左、右子数递归判断。
class Solution: def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool: if not root: return False if not root.left and not root.right: return root.val == targetSum return self.hasPathSum(root.left, targetSum-root.val) or self.hasPathSum(root.right, targetSum-root.val)
