算法工程师的日常
0%

二叉树

发表于 更新于 分类于 ，

总结

大纲

微信截图_20231210121917.png

相关细节

  1. 夹在state.append和dfs(root, state)中间的判断是否target_sum正确的时候，不需要加return，不然会导致运行结果的问题。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:
        res = []
        def dfs(root, state):
            if not root:
                return
            state.append(root.val)
            if not root.left and not root.right:
                res.append(state[:]) # 这里不要return
            dfs(root.left, state)
            dfs(root.right, state)
            state.pop()
        dfs(root, [])
        return ["->".join([str(i) for i in s]) for s in res]

遍历操作

介绍

树结构如下

先序：1 2 4 6 7 8 3 5
中序：4 7 6 8 2 1 3 5
后序：7 8 6 4 2 5 3 1

递归

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


root = TreeNode(1, left=TreeNode(2, left=TreeNode(3), right=TreeNode(4)),
                right=TreeNode(5, left=TreeNode(6), right=TreeNode(7)))

# 前序遍历
res = []
def preOrder(root):
    if not root:
        return
    res.append(root.val)
    preOrder(root.left)
    preOrder(root.right)
preOrder(root)
print("前序结果是：", res)


# 中序遍历
res = []
def inOrder(root):
    if not root:
        return
    inOrder(root.left)
    res.append(root.val)
    inOrder(root.right)
inOrder(root)
print("中序结果是：", res)


# 后序遍历
res = []
def postOrder(root):
    if not root:
        return
    postOrder(root.left)
    postOrder(root.right)
    res.append(root.val)
postOrder(root)
print("后序结果是：", res)

迭代

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
# 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


root = TreeNode(1, left=TreeNode(2, left=TreeNode(3), right=TreeNode(4)),
                right=TreeNode(5, left=TreeNode(6), right=TreeNode(7)))


# 前序
stack = [root]
res = []
while stack:
    node = stack.pop()
    res.append(node.val)
    if node.right:
        stack.append(node.right)
    if node.left:
        stack.append(node.left)
print("前序结果是：", res)

# 后序
stack = [root]
res = []
while stack:
    node = stack.pop()
    res.append(node.val)
    if node.left:
        stack.append(node.left)
    if node.right:
        stack.append(node.right)
print("后序结果是：", res)

# 中序,注意这里不能直接将root加入进去
stack = []
cur = root
res = []
while stack or cur: 
    if cur:
        stack.append(cur)
        cur = cur.left
    else:
        cur = stack.pop()
        res.append(cur.val)
        cur = cur.right
print("中序结果是：", res)

# 层序遍历
from _collections import deque
queue = deque([root])
while queue:
    temp = []
    for i in range(len(queue)):
        node = queue.popleft()
        temp.append(node.val)
        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)
    print(temp)
# 层序遍历2
from _collections import deque
queue = deque([root])
while queue:
    temp = []
    for i in range(len(queue)):
        node = queue.popleft()
        if node:
            temp.append(node.val)
            queue.append(node.left)
            queue.append(node.right)
    print(temp)

需要注意层序遍历1和层序遍历2的区别，层序遍历1中的queue只添加一些非None的节点，而层序遍历2中的话，连一些为None的节点也会添加，这点在对称二叉树中会用到第二种方法。

结构操作

翻转二叉树[226]

迭代题解如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# 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 invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        if not root:
            return root
        from collections import deque
        queue = deque([root])
        while queue:
            for i in range(len(queue)):
                node = queue.popleft()
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
                node.left, node.right = node.right, node.left
        return root

递归解法如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
# 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 invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        if not root:
            return root
        root.left, root.right = root.right, root.left
        self.invertTree(root.left)
        self.invertTree(root.right)
        return root

对称二叉树[101]

迭代解法如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def isSymmetric(self, root: Optional[TreeNode]) -> bool:
        if not root:
            return True
        from _collections import deque
        queue = deque([root])
        while queue:
            res = []
            for i in range(len(queue)):
                node = queue.popleft()
                if node:
                    res.append(node.val)
                    queue.append(node.left)
                    queue.append(node.right)
                else:
                    res.append(None)
            if res != res[::-1]:
                return False
        return True

递归解法如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# 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 isSymmetric(self, root: Optional[TreeNode]) -> bool:
        def check(p,q):
            if p and not q:
                return False
            if not p and q:
                return False
            if not p and not q:
                return True
            if p.val != q.val:
                return False
            return check(p.left, q.right) and check(p.right, q.left)       
        
        if not root:
            return True
        return check(root, root)

这题主要要单独开一个sub-function出来操作。

平衡二叉树[110]

递归解法

1
2
3
4
5
6
7
8
9
class Solution:
    def isBalanced(self, root: Optional[TreeNode]) -> bool:
        def get_height(root):
            if not root:
                return 0
            return 1 + max(get_height(root.left), get_height(root.right))
        if not root:
            return True
        return abs(get_height(root.left) - get_height(root.right)) <=1 and self.isBalanced(root.left) and self.isBalanced(root.right)

优化完后的递归的解法如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def isBalanced(self, root: Optional[TreeNode]) -> bool:
        def recu(root):
          if not root:
            return 0
          left = recu(root.left)
          if left==-1:
            return -1
          right = recu(root.right)
          if right==-1:
            return -1
          return max(left, right) + 1 if abs(left-right)<=1 else -1
        return recu(root)!=-1

深度和高度

完全二叉树的节点个数[222]

迭代解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# 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:
      if not root:
        return 0
      from collections import deque
      queue = deque([root])
      cnt = 0
      while queue:
        for i in range(len(queue)):
            node = queue.popleft()
            cnt += 1
            if node.left:
              queue.append(node.left)
            if node.right:
              queue.append(node.right)
      return cnt

递归解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# 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 __init__(self):
        self.cnt = 0

    def countNodes(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0
        self.cnt += 1
        self.countNodes(root.left)
        self.countNodes(root.right)
        return self.cnt

二叉树最大高度[104]

迭代解法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# 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 maxDepth(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0
        from collections import deque
        queue = deque([root])
        res = []
        while queue:
            temp = []
            for i in range(len(queue)):
                node = queue.popleft()
                temp.append(node.val)
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
            res.append(temp)
        return len(res)

递归法如下所示：

1
2
3
4
5
6
7
8
9
10
11
# 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 maxDepth(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0
        return 1 + max(self.maxDepth(root.left), self.maxDepth(root.right))

二叉树最小深度[111]

迭代法如下所示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# 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 minDepth(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0
        from collections import deque
        queue = deque([root])
        min_depth = 0
        while queue:
            min_depth += 1
            for i in range(len(queue)):
                node = queue.popleft()
                if node.left==None and node.right==None:
                    return min_depth
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
        return minDepth

递归法如下所示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# 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 minDepth(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0
        if not root.left and root.right:
            return 1 + self.minDepth(root.right) # 容易写成不加1
        if not root.right and root.left:
            return 1 + self.minDepth(root.left)
        return 1 + min(self.minDepth(root.left), self.minDepth(root.right))

路径问题

二叉树的所有路径[257]

迭代解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
    def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:
        if not root:
            return False
        if not root.left and not root.right:
          return [str(root.val)]
        from collections import deque
        queue = deque([root])
        queue2 = [str(root.val)]
        res = []
        while queue:
            for i in range(len(queue)):
              node = queue.popleft()
              node_value = queue2.pop(0)
              if not node.left and not node.right:
                  res.append(node_value)
              if node.left:
                  queue.append(node.left)
                  queue2.append(str(node_value) + "->" + str(node.left.val))
              if node.right:
                  queue.append(node.right)
                  queue2.append(str(node_value) + "->" + str(node.right.val))
        return res

递归解法

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
# 使用回溯1
class Solution:
    def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:
        res = []
        def dfs(root, state):
            if root:
                state.append(root.val)
                if not root.left and not root.right:
                    res.append("->".join([str(i) for i in state[:]]))
                    return
                if root.left:
                    dfs(root.left, state)
                    state.pop()
                if root.right:
                    dfs(root.right, state)
                    state.pop()
        dfs(root, [])
        return res
        
# [推荐写法] 回溯2
class Solution:
    def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:
        res = []
        def dfs(root, state):
            if not root:
                return
            state.append(root.val)
            if not root.left and not root.right:
                res.append(state[:])
            dfs(root.left, state)
            dfs(root.right, state)
            state.pop()
        dfs(root, [])
        return ["->".join([str(i) for i in s]) for s in res]
        
# 还有一种回溯的写法，不需要显示的调用pop函数
class Solution:
    def binaryTreePaths(self, root):
        """
        :type root: TreeNode
        :rtype: List[str]
        """
        def construct_paths(root, path):
            if root:
                path += str(root.val)
                if not root.left and not root.right:  # 当前节点是叶子节点
                    paths.append(path)  # 把路径加入到答案中
                else:
                    path += '->'  # 当前节点不是叶子节点，继续递归遍历
                    construct_paths(root.left, path)
                    construct_paths(root.right, path)

        paths = []
        construct_paths(root, '')
        return paths

路径总和[112]

迭代解法如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
      if not root:
        return False
      from collections import deque
      queue = deque([root]) # 使用了两个deque
      queue2 = deque([root.val])
      while queue:
        for i in range(len(queue)):
          node = queue.popleft()
          node_value = queue2.popleft()
          if node.left==None and node.right==None and node_value==targetSum:
            return True
          if node.left:
            queue.append(node.left)
            queue2.append(node_value+node.left.val)
          if node.right:
            queue.append(node.right)
            queue2.append(node_value+node.right.val)
      return False

递归解法如下

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
# 正确解答1
class Solution:
    def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
        if not root:
            return False
        if not root.left and not root.right:
            return targetSum == root.val
        return self.hasPathSum(root.left, targetSum - root.val) or self.hasPathSum(root.right, targetSum - root.val)
# [推荐写法]正确解答2【为了和后面的112保持一致，使用该解法】
class Solution:
    def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
        if not root:
            return False
        targetSum = targetSum - root.val
        if not root.left and not root.right and targetSum==0:
            return True
        return self.hasPathSum(root.left, targetSum) or self.hasPathSum(root.right, targetSum)
# 错写
class Solution:
    def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
        if not root:
            return False
        if not root.left and not root.right and targetSum==0: # 注意
            return False # 注意
        return self.hasPathSum(root.left, targetSum - root.val) or self.hasPathSum(root.right, targetSum - root.val)

路径总和 II[113]

递归解法如下

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
# 回溯解法1，按照标准的回溯来写的
class Solution:
    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> List[List[int]]:
        res = []
        def dfs(root, state):
            if not root:
                return
            state.append(root.val)
            if not root.left and not root.right:
                if sum(state[:])==targetSum:
                    res.append(state[:])
                    return
            if root.left:
                dfs(root.left, state)
                state.pop()
            if root.right:
                dfs(root.right, state)
                state.pop()
        dfs(root, [])
        return res
        
# [推荐写法]回溯解法2， 按照标准回溯来
class Solution:
    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> List[List[int]]:
        ret = list()
        def dfs(root, state):
            if not root:
                return
            state.append(root.val)
            if not root.left and not root.right and sum(state[:]) == targetSum:
                ret.append(state[:])
            dfs(root.left, state)
            dfs(root.right, state)
            state.pop()
        dfs(root, [])
        return ret
        
# 回溯解法2，使用非标准的回溯来写的
class Solution:
    def pathSum(self, root: TreeNode, targetSum: int) -> List[List[int]]:
        ret = list()
        path = list()
        
        def dfs(root: TreeNode, targetSum: int):
            if not root:
                return
            path.append(root.val)
            targetSum -= root.val
            if not root.left and not root.right and targetSum == 0:
                ret.append(path[:])
            dfs(root.left, targetSum)
            dfs(root.right, targetSum)
            path.pop()
        
        dfs(root, targetSum)
        return ret
        
# 回溯解法3，使用非标准回溯来
class Solution:
    def pathSum(self, root, targetSum):
        ret = list()
        path = list()

        def dfs(root: TreeNode):
            if not root:
                return
            path.append(root.val)
            if not root.left and not root.right and sum(path[:]) == targetSum:
                ret.append(path[:])
            dfs(root.left)
            dfs(root.right)
            path.pop()

        dfs(root)
        return ret

非标准的意思是，这里的path是一个不在dfs中传进去的值

路径总和III[437]

我的解法如下，超时了,妈的不打算改了就这样吧

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> int:
        res = []
        def dfs(root, state):
            if not root:
                return
            state.append(root.val)
            if sum(state[:])==targetSum:
                res.append(state[:])
            dfs(root.left, state)
            dfs(root.right, state)
            state.pop()

        def dfs2(root):
            if not root:
                return
            dfs(root,[])
            dfs2(root.left)
            dfs2(root.right)

        dfs2(root)
        return len(res)

二叉树中的最大路径和[124]

位于 https://leetcode.cn/problems/binary-tree-maximum-path-sum/description/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def __init__(self):
        self.max_sum = -88

    def maxPathSum(self, root: Optional[TreeNode]) -> int:
        def maxGain(root):
            if not root:
                return 0
            leftGain = max(maxGain(root.left), 0)
            rightGrain = max(maxGain(root.right), 0)
            cur_root_gain = root.val + leftGain + rightGrain
            if cur_root_gain > self.max_sum:
                self.max_sum = cur_root_gain
            return root.val + max(rightGrain,leftGain) #写错为root.val + rightGrain + leftGain
        maxGain(root)
        return self.max_sum

注意这里的maxGain是需要定义好的，返回的值是以当前节点为开始或者结束的收益值，因此需要写成root.val+max(rightGain, leftGain)

二叉树的最近公共祖先[236]

递归法如下，最主要的点在代码中已经说了

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
26
27
28
29
30
31
32
33
34
35
36
37
# 错误解法
class Solution(object):
    def lowestCommonAncestor(self, root, p, q):
        """
        :type root: TreeNode
        :type p: TreeNode
        :type q: TreeNode
        :rtype: TreeNode
        """
        if not root:
            return root
        if not root.left and root.right:
            return self.lowestCommonAncestor(root.right, p, q)
        if not root.right and root.left:
            return self.lowestCommonAncestor(root.left, p, q)
        left = self.lowestCommonAncestor(root.left, p, q)
        right = self.lowestCommonAncestor(root.right, p, q)
        if not left:
            return right
        if not right:
            return left
        if left and right:
            return root
# 正确解法
class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        if not root:
            return root
        if root==p or root==q: # 最重要的点
            return root
        left = self.lowestCommonAncestor(root.left, p, q)
        right = self.lowestCommonAncestor(root.right, p, q)
        if not left:
            return right
        if not right:
            return left
        return root

构造二叉树

最大二叉树[654]

迭代法

1
2
3
4
5
6
7
8
9
class Solution:
    def constructMaximumBinaryTree(self, nums: List[int]) -> Optional[TreeNode]:
        if not nums:
            return
        max_index = nums.index(max(nums))
        root = TreeNode(val=nums[max_index])
        root.left = self.constructMaximumBinaryTree(nums[:max_index])
        root.right = self.constructMaximumBinaryTree(nums[max_index+1:])
        return root

合并二叉树[617]

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def mergeTrees(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> Optional[TreeNode]:
        if not root1 and not root2:
            return
        if not root1 and root2:
            return root2
        if not root2 and root1:
            return root1
        root = TreeNode(root1.val + root2.val)
        root.left = self.mergeTrees(root1.left, root2.left)
        root.right = self.mergeTrees(root1.right, root2.right)
        return root

从前序与中序遍历序列构造二叉树[105]

递归方法如下

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
        if not preorder:
            return
        if not inorder:
            return
        root = TreeNode(preorder[0])
        inorder_index = inorder.index(preorder[0])
        root.left = self.buildTree(preorder[1:inorder_index+1], inorder[:inorder_index])
        root.right = self.buildTree(preorder[inorder_index+1:], inorder[inorder_index+1:])
        return root

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

递归解法如下

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def buildTree(self, inorder: List[int], postorder: List[int]) -> Optional[TreeNode]:
        if not inorder:
            return
        if not postorder:
            return
        root = TreeNode(postorder[-1])
        inorder_index = inorder.index(postorder[-1])
        root.left = self.buildTree(inorder[:inorder_index], postorder[:inorder_index])
        root.right = self.buildTree(inorder[inorder_index+1:], postorder[inorder_index:-1])
        return root

二叉搜索树

将有序数组转换为二叉搜索树[108]

1
2
3
4
5
6
7
8
9
class Solution:
    def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:
        if len(nums)==0:
            return None
        mid = int(len(nums)/2)
        root = TreeNode(nums[mid])
        root.left = self.sortedArrayToBST(nums[:mid])
        root.right = self.sortedArrayToBST(nums[mid+1:])
        return root

二叉搜索树中的搜索[700]

迭代法，就是类似链表

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def searchBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
        cur = root
        while cur:
            f = cur.val
            if f < val:
                cur = cur.right
            elif f > val:
                cur = cur.left
            else:
                return cur
        return None

递归法

1
2
3
4
5
6
7
8
9
10
class Solution:
    def searchBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
        if not root:
            return None
        if root.val == val:
            return root
        elif root.val > val:
            return self.searchBST(root.left, val)
        elif root.val < val:
            return self.searchBST(root.right, val)

验证二叉搜索树[98]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        res = []
        def inOrder(root):
            if not root:
                return
            inOrder(root.left)
            res.append(root.val)
            inOrder(root.right)
        inOrder(root)
        for i in range(len(res)-1):
          if res[i+1] <= res[i]:
            return False
        return True

二叉搜索树的最小绝对差[530]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution(object):    
    def getMinimumDifference(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        res = []
        def inorder(root):
            if not root:
                return
            inorder(root.left)
            res.append(root.val)
            inorder(root.right)
        inorder(root)
        mins = float("inf")
        for i in range(len(res)-1):
            mins = min(mins, abs(res[i+1] - res[i]))
        return mins

二叉搜索树中的众数[501]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution(object):
    def findMode(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        res = []
        def inorder(root):
            if not root:
                return
            inorder(root.left)
            res.append(root.val)
            inorder(root.right)
        inorder(root)
        from collections import Counter
        cnt = Counter(res)
        from collections import defaultdict
        new_d = defaultdict(list)
        for k, v in cnt.items():
            new_d[v].append(k)
        new_d = sorted(new_d.items(),key=lambda x:-x[0])
        return new_d[0][1]

二叉搜索树的最近公共祖先[235]

递归解法如下

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        if not root:
            return root
        if root == p or root == q:
            return root
        if root.val < min(p.val, q.val):
            return self.lowestCommonAncestor(root.right, p, q)
        if root.val > max(p.val, q.val):
            return self.lowestCommonAncestor(root.left, p, q)
        else:
            return root

二叉树的最近公共祖先[236]

递归法如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
# 正确解法
class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        if not root:
            return root
        if root==p or root==q:
            return root
        left = self.lowestCommonAncestor(root.left, p, q)
        right = self.lowestCommonAncestor(root.right, p, q)
        if not left:
            return right
        if not right:
            return left
        return root

二叉搜索树中的插入操作[701]

迭代法

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
26
27
28
class Solution:
    def insertIntoBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
        res_trees = []
        def inorder(root):
            if not root:
                return
            inorder(root.left)
            res_trees.append(root)
            inorder(root.right)
        if not root:
            return TreeNode(val)
        inorder(root)

        if val < res_trees[0].val:
            res_trees[0].left = TreeNode(val)
        
        if val > res_trees[-1].val:
            res_trees[-1].right = TreeNode(val)

        for i in range(len(res_trees)-1):
            if val>res_trees[i].val and val<res_trees[i+1].val:
                left = res_trees[i]
                right = res_trees[i+1]
                if left.right==None:
                    left.right = TreeNode(val)
                elif right.left==None:
                    right.left = TreeNode(val)
        return root

官方迭代法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def insertIntoBST(self, root: TreeNode, val: int) -> TreeNode:
        if not root:
            return TreeNode(val)
        
        pos = root
        while pos:
            if val < pos.val:
                if not pos.left:
                    pos.left = TreeNode(val)
                    break
                else:
                    pos = pos.left
            else:
                if not pos.right:
                    pos.right = TreeNode(val)
                    break
                else:
                    pos = pos.right
        
        return root

删除二叉搜索树中的节点[450]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution:
    def deleteNode(self, root: Optional[TreeNode], key: int) -> Optional[TreeNode]:
        if not root:
            return None
        if root.val > key:
            root.left = self.deleteNode(root.left, key)
        elif root.val < key:
            root.right = self.deleteNode(root.right, key)
        else:
            # 判断root点的情况
            if not root.left and root.right:
                return root.right
            if not root.right and root.left:
                return root.left           
            if not root.left and not root.right:
                return None    
            if root.left and root.right:
                # 找到最左边的节点
                t = node = root.right
                while node.left:
                    node = node.left
                node.left = root.left
                return t
        return root

修剪二叉搜索树[669]

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
26
27
28
29
30
# 错误解法
class Solution:
    def trimBST(self, root: Optional[TreeNode], low: int, high: int) -> Optional[TreeNode]:
        if not root:
            return root
        if root and root.val < low:
            root = root.right
        if root and root.val > high:
            root = root.left
        if root and root.left and root.left.val < low:
            root.left = root.left.right
        if root and root.right and root.right.val > high:
            root.right = root.right.left
        if root and root.left:
            self.trimBST(root.left, low, high)
        if root and root.right:
            self.trimBST(root.right, low, high)
        return root
# 【推荐解法】
class Solution:
    def trimBST(self, root: Optional[TreeNode], low: int, high: int) -> Optional[TreeNode]:
        if not root:
            return root
        if root.val < low:
            return self.trimBST(root.right, low, high)
        elif root.val > high:
            return self.trimBST(root.left, low, high)
        root.left = self.trimBST(root.left, low, high)
        root.right = self.trimBST(root.right, low, high)
        return root

把二叉搜索树转换为累加树[538]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def convertBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        res = []
        def inorder(root):
            if not root:
                return
            inorder(root.left)
            res.append(root)
            inorder(root.right)
        inorder(root)
        res=res[::-1]
        for i in range(1,len(res)):
            res[i].val = res[i].val + res[i-1].val
        return root

把二叉搜索树转换为累加树[538]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def convertBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        res = []
        def inorder(root):
            if not root:
                return
            inorder(root.left)
            res.append(root)
            inorder(root.right)
        inorder(root)
        res=res[::-1]
        for i in range(1,len(res)):
            res[i].val = res[i].val + res[i-1].val
        return root