二叉树110|257|404
110平衡二叉树
# 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 isBalanced(self, root: Optional[TreeNode]) -> bool: if self.height(root) == -1: return False else: return True def height(self, node) -> int: if not node: return 0 height_left = self.height(node.left) height_right = self.height(node.right) if height_left == -1 or height_right == -1: return -1 if abs(height_left - height_right) > 1: return -1 else: height_node = max(height_left, height_right) + 1 return height_node
257二叉树的所有路径
# 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 binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]: path = [] result = [] if not root: return result return self.traversal(root, path, result) def traversal(self, node, path, result) -> List: path.append(node.val) if not node.left and not node.right: path_str = "->".join(str(item) for item in path) result.append(path_str) return result if node.left: self.traversal(node.left, path, result) path.pop() if node.right: self.traversal(node.right, path, result) path.pop() return result
404左叶子之和
# 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 sumOfLeftLeaves(self, root: Optional[TreeNode]) -> int: return self.getSum(root) def getSum(self, node) -> int: if not node: return 0 left_val = self.getSum(node.left) right_val = self.getSum(node.right) if node.left and not node.left.left and not node.left.right: left_val = node.left.val sum_left_leaves = left_val + right_val return sum_left_leaves