算法训练第十五天

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:
        ans = [True]
        a = self.find(root,ans)
        return ans[0]

    def find(self,node,ans):
        if node is None:
            return 0
        left = self.find(node.left,ans)
        right = self.find(node.right,ans)
        if abs(left-right)>1:
            ans[0] = False
        return max(left,right)+1

257.二叉树的所有路径

代码：

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    import copy
    def binaryTreePaths(self, root):
        """
        :type root: Optional[TreeNode]
        :rtype: List[str]
        """
        ans = []
        res = []
        self.find(root,res,ans)
        return ans
    
    def find(self,node,res,ans):
        res.append(str(node.val))
        if node.left is None and node.right is None:
            ans.append(copy.deepcopy('->'.join(res)))
            
            res.pop()
            return
        if node.left:
            self.find(node.left,res,ans)
        if node.right:
            self.find(node.right,res,ans)
        res.pop()

        

404.左叶子之和

代码：

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def sumOfLeftLeaves(self, root):
        """
        :type root: Optional[TreeNode]
        :rtype: int
        """
        ans = []
        lf=False
        self.find(root,ans,lf)
        return sum(ans)

    def find(self,node,ans,lf):
        if node.left is None and node.right is None:
            if lf:
                ans.append(node.val)
        if node.left:
            self.find(node.left,ans,True)
        if node.right:
            self.find(node.right,ans,False)

222.完全二叉树的节点个数

代码：

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def countNodes(self, root):
        """
        :type root: Optional[TreeNode]
        :rtype: int
        """
        ans = []
        self.find(root,ans)
        return len(ans)

    def find(self,node,ans):
        if node:
            ans.append(node.val)
            self.find(node.left,ans)
            self.find(node.right,ans)