110.平衡二叉树

力扣链接
给定一个二叉树，判断它是否是 平衡二叉树（所有节点的左右子树深度不会超过1）

思路 后序遍历

如果判断到子树不是平衡二叉树，就返回-1，这个-1会一路向上返回到根节点

class Solution:
    def isBalanced(self, root: Optional[TreeNode]) -> bool:
        res = self.getheight(root)
        if res == -1:
            return False
        else:
            return True
    def getheight(self, node):
        if node == None:
            return 0 # 空节点的高度为0，叶子结点的高度为1
        # 左
        l_d = self.getheight(node.left)
        if l_d == -1: # 说明左子树不是平衡的，直接向上传递-1
            return -1
        # 右
        r_d = self.getheight(node.right)
        if r_d == -1:# 说明右子树不是平衡的，直接向上传递-1
            return -1
        # 中
        if abs(l_d-r_d)>1:
            return -1
        else: 
            return 1 + max(l_d,r_d) # 返回当前节点的高度

257.二叉树的所有路径

力扣链接
给你一个二叉树的根节点 root ，按 任意顺序 ，返回所有从根节点到叶子节点的路径。叶子节点 是指没有子节点的节点。

思路 前序遍历

要求从根节点指向叶子的路径，所以需要前序遍历（中左右）.
从根节点向下走，走到叶子结点后，往上退以找到别的路径，这个往上退的过程就叫回溯。

res存放结果，path存放单条路径

class Solution:
    def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:
        res = []
        path = []
        if root == None:
            return res
        self.traversal(root,path,res)
        return res
        
    def traversal(self,cur,path,res):
        # 中
        path.append(cur.val)
        if cur.left == None and cur.right == None: # 到达叶子节点
            spath = '->'.join(map(str,path)) # 数组转化为字符串，并且在中间加->
            res.append(spath)
            return
        # 左
        if cur.left:
            self.traversal(cur.left, path, res)
            path.pop()# 到达终止条件了，回溯
        # 右
        if cur.right:
            self.traversal(cur.right,path,res)
            path.pop()

404.左叶子之和

力扣链接
给定二叉树的根节点 root ，返回所有左叶子之和。

思路

判断当前节点是不是左叶子是无法判断的，必须要通过节点的父节点来判断其左孩子是不是左叶子。
如果该节点的左节点不为空，该节点的左节点的左节点为空，该节点的左节点的右节点为空，则找到了一个左叶子

class Solution:
    def sumOfLeftLeaves(self, root: Optional[TreeNode]) -> int:
        if root == None:
            return 0
        if root.left == None and root.right == None:
            return 0
        
        leftval = self.sumOfLeftLeaves(root.left)
        # 该节点的左节点不为空，该节点的左节点的左节点为空，该节点的左节点的右节点为空，则找到了一个左叶子
        if root.left and root.left.left == None and root.left.right == None:
            leftval = root.left.val
        
        rightval = self.sumOfLeftLeaves(root.right)

        res = leftval + rightval
        return res