algorithm

Python刷题录

宋正兵 on 2022-03-21

tips:

  • python中，None、False、0、''、[]、{}、()等一系列代表空和无的对象都被视为’False

二叉树

二叉树的前序遍历

144. 二叉树的前序遍历 - 力扣

方法一：迭代

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        ans = []
        if root is None:
            return ans
        stack = list()
        stack.append(root)
        while len(stack) > 0:
            root = stack.pop()
            ans.append(root.val)
            if root.right is not None:
                stack.append(root.right)
            if root.left is not None:
                stack.append(root.left)
        return ans

方法二：递归

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def preorder(self, root, ans):
        if root is None:
            return
        ans.append(root.val)
        self.preorder(root.left, ans)
        self.preorder(root.right, ans)

    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        ans = list()
        self.preorder(root, ans)
        return ans

二叉树的中序遍历

94. 二叉树的中序遍历 - 力扣

方法一：迭代

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        ans = list()
        if root is None:
            return ans
        stack = list()
        while len(stack) > 0 or root is not None:
            while root is not None:           
                stack.append(root)
                root = root.left
            root = stack.pop()
            ans.append(root.val)
            root = root.right
        return ans

方法二：递归

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def inorder(self, root, ans):
        if root is None:
            return ans
        self.inorder(root.left, ans)
        ans.append(root.val)
        self.inorder(root.right, ans)
        return ans
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        ans = list()
        self.inorder(root, ans)
        return ans

二叉树的后序遍历

145. 二叉树的后序遍历 - 力扣

方法一：迭代

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        ans = list()
        if root is None:
            return ans
        stack = list()
        stack.append(root)
        while len(stack) > 0:
            root = stack.pop()
            ans.append(root.val)
            if root.left is not None:
                stack.append(root.left)
            if root.right is not None:
                stack.append(root.right)
        ans.reverse()
        return ans

方法二：递归

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def postorder(self, root, ans):
        if root is None:
            return
        self.postorder(root.left, ans)
        self.postorder(root.right, ans)
        ans.append(root.val)
    def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        ans = list()
        self.postorder(root, ans)
        return ans

二叉树的层序遍历

102. 二叉树的层序遍历 - 力扣

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        ans = list()
        if root is None:
            return ans
        queue = list()
        queue.append(root)
        while len(queue) > 0:
            count = len(queue)
            temp_ans = list()
            while count > 0:
                count -= 1
                root = queue.pop(0)
                temp_ans.append(root.val)
                if root.left is not None:
                    queue.append(root.left)
                if root.right is not None:
                    queue.append(root.right)
            ans.append(temp_ans)
        return ans

二叉树的层序遍历Ⅱ

107. 二叉树的层序遍历 II - 力扣

题目大意：从下往上的层序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def levelOrderBottom(self, root: TreeNode) -> List[List[int]]:
        ans = list()
        if root is None:
            return ans
        queue = list()
        queue.append(root)
        while len(queue) > 0:
            count = len(queue)
            temp_ans = list()
            while count > 0:
                count -= 1
                root = queue.pop(0)
                temp_ans.append(root.val)
                if root.left is not None:
                    queue.append(root.left)
                if root.right is not None:
                    queue.append(root.right)
            ans.insert(0, temp_ans)
        return ans

二叉树的锯齿形层次遍历

103. 二叉树的锯齿形层序遍历 - 力扣

题目大意：层序遍历，但每一层的遍历方向不同。第一层从左到右，第二层从右到左……

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution:
    def zigzagLevelOrder(self, root: TreeNode) -> List[List[int]]:
        ans = list()
        if root is None:
            return ans
        queue = list()
        queue.append(root)
        left_first = False
        while len(queue) > 0:
            left_first = not left_first
            count = len(queue)
            temp_ans = list()
            while count > 0:
                count -= 1
                root = queue.pop(0)
                if left_first == True:
                    temp_ans.append(root.val)
                else:
                    temp_ans.insert(0, root.val)
                if root.left is not None:
                    queue.append(root.left)
                if root.right is not None:
                    queue.append(root.right)
            ans.append(temp_ans)
        return ans

二叉树的最大深度

104. 二叉树的最大深度 - 力扣（LeetCode）

题目大意：给定一颗二叉树的根节点，返回从根节点到叶子节点的最长路径距离。

1
2
3
4
5
6
7
class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        if root is None:
            return 0
        left_depth = self.maxDepth(root.left)
        right_depth = self.maxDepth(root.right)
        return max(left_depth, right_depth) + 1

平衡二叉树

110. 平衡二叉树 - 力扣（LeetCode）

题目大意：给定一颗二叉树，判断其是否为高度平衡的。

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def isBalanced(self, root: TreeNode) -> bool:
        return self.get_depth(root) >= 0
        
    def get_depth(self, root: TreeNode) -> int:
        if root is None:
            return 0
        left_depth = self.get_depth(root.left)
        right_depth = self.get_depth(root.right)
        if (left_depth < 0) or (right_depth < 0) or abs(left_depth - right_depth) > 1:
            return -1
        return max(left_depth, right_depth) + 1

二叉树中的最大路径和

124. 二叉树中的最大路径和 - 力扣（LeetCode）

题目大意：找出二叉树中的最大路径和，路径不需要经过root节点。

主要使用递归的思想。完成一个函数 max_gain(node) ，计算二叉树中的一个节点的最大贡献值，即以该节点为根节点的子树中寻找以该节点为起点的一条路径，使得该路径上的节点值之和最大。

具体而言，计算如下：

  • 空节点的最大贡献为0
  • 非空节点的最大贡献等于节点值与其子节点中的最大贡献值之和

使用全局变量 max_sum 来存储最大路径和，在递归过程中更新它的值。

节点的贡献值是节点所在的路径！对于当前节点的贡献值是节点值+MAX（左节点的最大贡献，右节点的最大贡献）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution:
    def __init__(self):
        self.max_sum = float("-inf")

    def maxPathSum(self, root: TreeNode) -> int:
        def max_gain(node):
            if not node:
                return 0

            # 递归计算左右子节点的最大贡献值
            # 只有在最大贡献值大于 0 时，才会选取对应子节点
            left_gain = max(max_gain(node.left), 0)
            right_gain = max(max_gain(node.right), 0)
            
            # 节点的最大路径和取决于该节点的值与该节点的左右子节点的最大贡献值
            price_newpath = node.val + left_gain + right_gain
            
            # 更新答案
            self.max_sum = max(self.maxSum, price_newpath)
        
            # 返回节点的最大贡献值
            return node.val + max(left_gain, right_gain)
   
        max_gain(root)
        return self.max_sum

二叉树的最近公共祖先

236. 二叉树的最近公共祖先 - 力扣（LeetCode）

题目大意：找出二叉树中两个给定节点的最近公共祖先（LCA）。

通过判断左右子树是否包含目标节点来找LCA，有如下几种情况：

  1. 左右子树都不包含目标节点，返回None
  2. 左右子树都包含目标节点，说明左右子树各有一个，当前root节点就是LCA，返回root
  3. 左子树不包含，右子树包含，返回right表明右子树包含
  4. 左子树包含，右子树不包含，返回left表明左子树包含
1
2
3
4
5
6
7
8
9
10
class Solution:
    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:
        #当root为目标节点
        if not root or root == p or root == q: return root
        left = self.lowestCommonAncestor(root.left, p, q)
        right = self.lowestCommonAncestor(root.right, p, q)
        if not left and not right: return # 1.左右子树都不包含到目标节点
        if not left: return right # 3.右子树包含，左子树不包含
        if not right: return left # 4.左子树包含，右子树不包含
        return root # 2. 左右子树都包含



标签
algorithm