110. 平衡二叉树
自顶向下递归
1. 获得计算二叉树高度的函数
2. 对于遍历到的节点,首先计算左右子树的高度,看是否平衡
3. 在分别遍历到左右子树,判断左子树和右子树是否平衡
代码如下:
class Solution: def isBalanced(self, root: TreeNode) -> bool: def height(root: TreeNode) -> int: if not root: return 0 return max(height(root.left), height(root.right)) + 1 if not root: return True return abs(height(root.left) - height(root.right)) <= 1 and self.isBalanced(root.left) and self.isBalanced(root.right)
257. 二叉树的所有路径
深度优先搜索
class Solution: def binaryTreePaths(self, root): """ :type root: TreeNode :rtype: List[str] """ def construct_paths(root, path): if root: path += str(root.val) if not root.left and not root.right: # 当前节点是叶子节点 paths.append(path) # 把路径加入到答案中 else: path += '->' # 当前节点不是叶子节点,继续递归遍历 construct_paths(root.left, path) construct_paths(root.right, path) paths = [] construct_paths(root, '') return paths
广度优先搜索
class Solution: def binaryTreePaths(self, root: TreeNode) -> List[str]: paths = list() if not root: return paths node_queue = collections.deque([root]) path_queue = collections.deque([str(root.val)]) while node_queue: node = node_queue.popleft() path = path_queue.popleft() if not node.left and not node.right: paths.append(path) else: if node.left: node_queue.append(node.left) path_queue.append(path + '->' + str(node.left.val)) if node.right: node_queue.append(node.right) path_queue.append(path + '->' + str(node.right.val)) return paths
404. 左叶子之和
深度优先搜索
class Solution: def sumOfLeftLeaves(self, root: TreeNode) -> int: isLeafNode = lambda node: not node.left and not node.right def dfs(node: TreeNode) -> int: ans = 0 if node.left: ans += node.left.val if isLeafNode(node.left) else dfs(node.left) if node.right and not isLeafNode(node.right): ans += dfs(node.right) return ans return dfs(root) if root else 0
广度优先搜索
class Solution: def sumOfLeftLeaves(self, root: TreeNode) -> int: if not root: return 0 isLeafNode = lambda node: not node.left and not node.right q = collections.deque([root]) ans = 0 while q: node = q.popleft() if node.left: if isLeafNode(node.left): ans += node.left.val else: q.append(node.left) if node.right: if not isLeafNode(node.right): q.append(node.right) return ans