今日任务：

1. LeetCode110 平衡二叉树
2. LeetCode257 二叉树的所有路径
3. LeetCode404 左叶子之和

资料来源：

1. 代码随想录 | LeetCode110 平衡二叉树
2. 代码随想录 | LeetCode257 二叉树的所有路径
3. 代码随想录 | LeetCode404 左叶子之和

1 LeetCode110 平衡二叉树

输入：root = [3,9,20,null,null,15,7]
输出：true

输入：root = [1,2,2,3,3,null,null,4,4]
输出：false

输入：root = []
输出：true

递归+后序秒，高度要从递归函数一层一层传上来，如果有发现传上来的子树高度差超过1的，直接返回-1即可。这个-1最终会返回一开始的函数调用处，根据是否是-1返回True/False就行。

python
from typing import Optional

# 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:
        result = self.getHeight(root)
        if result == -1:
            return False
        else:
            return True

    def getHeight(self, root: TreeNode) -> int:
        if root is None:
            return 1
        left_height = self.getHeight(root.left)
        if left_height == -1:
            return -1
        right_height = self.getHeight(root.right)
        if right_height == -1:
            return -1
        if abs(right_height - left_height) > 1:
            return -1
        else:
            return 1 + max(right_height, left_height)

2 LeetCode257 二叉树的所有路径

输入：root = [1,2,3,null,5]
输出：["1->2->5","1->3"]

输入：root = [1]
输出：["1"]

前序+回溯。下面的代码的回溯是直接复制了一个字符串的那种隐式回溯，不太能看的出来，结束一层函数栈，它就自动回溯了。（应该不能叫回溯的，但是要说回溯也行吧）

python
from typing import Optional, List

# 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]:
        if root is None:
            return []
        result = self.get_path(root, "", [])
        return result

    def get_path(self, root: TreeNode, path: str, result: List[str]) -> List[str]:
        if path == "":
            path = str(root.val)
        else:
            path += "->" + str(root.val)
        if root.left is None and root.right is None:  # 是叶子节点
            result.append(path)
            return result
        if root.left is not None:
            result = self.get_path(root.left, path, result)
        if root.right is not None:
            result = self.get_path(root.right, path, result)
        return result

3 LeetCode404 左叶子之和

输入: root = [3,9,20,null,null,15,7] 
输出: 24 
解释: 在这个二叉树中，有两个左叶子，分别是 9 和 15，所以返回 24

输入: root = [1]
输出: 0

后序+递归。大体思路就是在递归的时候，在左叶子的上一层就先把左叶子找到，然后返回总和。有了这个思路之后就是递归三步走即可。迭代也是这个整体思路。

python
from typing import Optional

# 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:
        if root is None or (root.left is None and root.right is None):
            return 0
        return self.travelsal(root)

    def travelsal(self, root: TreeNode) -> int:
        # 终止条件
        if root is None:
            return 0
        if root.left is None and root.right is None:
            return 0
        left_sum = self.travelsal(root.left)  # 这是为了向下递归 和下一句语句不冲突
        if root.left is not None and root.left.left is None and root.left.right is None:  # 是不是左孩子的判断
            left_sum += root.left.val
        right_sum = self.travelsal(root.right)  # 向下递归
        return left_sum + right_sum  # 返回结果