算法训练营第十四天｜110. 平衡二叉树、257. 二叉树的所有路径、404. 左叶子之和、222.完全二叉树的节点个数

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 not root:
            return True

        return self.judgeBalance(root)    
    
    def judgeBalance(self, node: Optional[TreeNode]) -> bool:
        if not node:
            return True
            
        if not node.left and not node.right:
            return True

        judge_left = self.judgeBalance(node.left)
        judge_right = self.judgeBalance(node.right)
        if not (judge_left and judge_right):
            return False
        left_depth = self.getdepth(node.left)
        right_depth = self.getdepth(node.right)
        
        balance = abs(left_depth - right_depth)

        if balance > 1:
            return False

        return True
        

    def getdepth(self, node: Optional[TreeNode]) -> int:
        
        if not node:
            return 0
        
        left_depth = self.getdepth(node.left)
        right_depth = self.getdepth(node.right)
        
        return max(left_depth, right_depth) + 1
            

257. 二叉树的所有路径

题目

思路与解法

第一想法： 使用递归的方法，在递归的方法上传一个path参数

class Solution:
    def binaryTreePaths(self, root:Optional[TreeNode]) -> List[str]:
        self.all_path = []
        if not root:
            return all_path
        path = []
        self.get_path(path, root)
        return self.all_path

    def get_path(self, path, node:Optional[TreeNode]):
        if not node:
            return 

        path.append(str(node.val))

        if not node.left and not node.right:
            self.all_path.append('->'.join(path))
        
        self.get_path(path, node.left)
        self.get_path(path, node.right)
        path.pop()

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:
        self.sum_left = 0
        self.get_left(root)
        return self.sum_left



    def get_left(self, node:Optional[TreeNode]):
        if not node:
            return 

        if node.left:
            if not node.left.left and not node.left.right: 
                self.sum_left += int(node.left.val)
            self.get_left(node.left)
        if node.right:
            self.get_left(node.right)
        

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

题目

思路与解法

**第一思路：**遍历所有结点

# 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 countNodes(self, root: Optional[TreeNode]) -> int:
        
        self.count = 0
        self.get_allnum(root)
        return self.count

    def get_allnum(self, node):
        if not node:
            return 0

        self.count += 1

        if node.left:
            self.get_allnum(node.left)
        
        if node.right:
            self.get_allnum(node.right)