110. 平衡二叉树

思路：后序遍历，由下往上回溯

# 在Python中，:= 是一个赋值表达式，也被称为“海象运算符”（walrus operator），它在Python 3.8及以后的版本中引入。这个运算符允许你在表达式中赋值，并且可以立即使用赋值的结果。
class Solution:
    def isBalanced(self, root: TreeNode) -> bool:
        if self.get_height(root) != -1:
            return True
        else:
            return False

    def get_height(self, root: TreeNode) -> int:
        # Base Case
        if not root:
            return 0
        # 左
        if (left_height := self.get_height(root.left)) == -1:
            return -1
        # 右
        if (right_height := self.get_height(root.right)) == -1:
            return -1
        # 中
        if abs(left_height - right_height) > 1:
            return -1
        else:
            return 1 + max(left_height, right_height)

257. 二叉树的所有路径

思路：递归+回溯

# Definition for a binary tree node.
class Solution:
    def traversal(self, cur, path, result):
        path.append(cur.val)  # 中
        if not cur.left and not cur.right:  # 到达叶子节点
            sPath = '->'.join(map(str, path))
            result.append(sPath)
            return
        if cur.left:  # 左
            self.traversal(cur.left, path, result)
            path.pop()  # 回溯
        if cur.right:  # 右
            self.traversal(cur.right, path, result)
            path.pop()  # 回溯

    def binaryTreePaths(self, root):
        result = []
        path = []
        if not root:
            return result
        self.traversal(root, path, result)
        return result

迭代：

class Solution:
    def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:
        stack, path_st, result = [root], [str(root.val)], []

        while stack:
            cur = stack.pop()
            path = path_st.pop()
            # 如果当前节点为叶子节点，添加路径到结果中
            if not (cur.left or cur.right):
                result.append(path)
            
            if cur.left:
                stack.append(cur.left)
                path_st.append(path + '->' + str(cur.left.val))
            if cur.right:
                stack.append(cur.right)
                path_st.append(path + '->' + str(cur.right.val))

        return result

404. 左叶子之和

思路：要在父节点判断左子叶是否存在，到子节点那一层返回0即可

递归法：

class Solution:
    def sumOfLeftLeaves(self, root):
        if root is None:
            return 0
        if root.left is None and root.right is None:
            return 0
        
        leftValue = self.sumOfLeftLeaves(root.left)  # 左
        if root.left and not root.left.left and not root.left.right:  # 左子树是左叶子的情况
            leftValue = root.left.val
            
        rightValue = self.sumOfLeftLeaves(root.right)  # 右

        sum_val = leftValue + rightValue  # 中
        return sum_val