算法之美

二叉树

104. 二叉树的最大深度

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def maxDepth(self, root):
        if not root:
            return 0
        list = [root]
        length = 0
        #层次遍历
        while list:
            list1 = []
            for i in list:
                if i.left:
                    list1.append(i.left)
                if i.right:
                    list1.append(i.right)
            list = list1
            length += 1
        return length

剑指 Offer 55 – II. 平衡二叉树

性质:平衡二叉树深度=max(左子树深度,右子树深度) + 1

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def isBalanced(self, root):
        def recur(root):
            if not root:
                return 0
            left = recur(root.left)
            if left == -1:
                return -1
            right = recur(root.right)
            if right == -1:
                return -1
            if abs(left - right) <= 1:
                return max(left,right) + 1
            else:
                return -1
        return recur(root) != -1

剑指 Offer 07. 重建二叉树(前序+中序)

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def buildTree(self, preorder, inorder):
        if not preorder :
            return 
        # 根节点为前序遍历第一位
        root = TreeNode(preorder[0])
        #找到根节点在中序遍历中的位置
        index = inorder.index(preorder[0])

        left_pre = preorder[1:index+1]
        left_bac = inorder[:index]
        right_pre = preorder[index+1:]
        right_bac = inorder[index+1:]

        #构建左子树和右子树
        root.left = self.buildTree(left_pre,left_bac)
        root.right = self.buildTree(right_pre,right_bac)
        return root

106. 从中序与后序遍历序列构造二叉树

和上题一样的思路

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def buildTree(self, inorder: List[int], postorder: List[int]) -> TreeNode:
        if not inorder:
            return 
        root = TreeNode(postorder[-1])
        index = inorder.index(postorder[-1])

        left_pre = inorder[:index]
        left_bac = postorder[:index]
        right_pre = inorder[index+1:]
        right_bac = postorder[index:-1]

        root.left = self.buildTree(left_pre,left_bac)
        root.right = self.buildTree(right_pre,right_bac)
        return root

107. 二叉树的层次遍历 II

方法一:方法好笨,最后为什么会多出来一个空列表捏?

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def levelOrderBottom(self, root: TreeNode) -> List[List[int]]:
        if not root :
            return []
        list = [root]
        list_all = []
        list_all.append([root.val])
        while list:
            list1 = []
            list2 = []
            for i in list:
                if i.left:
                    list1.append(i.left)
                    list2.append(i.left.val)
                if i.right:
                    list1.append(i.right)
                    list2.append(i.right.val)
            list = list1
            list_all.append(list2)
        list_all.pop()
        list_all.reverse()
        return list_all


二叉树已关闭评论