二叉树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