LeetCodeCampsDay18二叉树part06

…

236. 二叉树的最近公共祖先

https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

示例 1：

img

1
2
3
输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出：3
解释：节点 5 和节点 1 的最近公共祖先是节点 3 。

示例 2：

img

1
2
3
输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出：5
解释：节点 5 和节点 4 的最近公共祖先是节点 5 。因为根据定义最近公共祖先节点可以为节点本身。

示例 3：

1
2
输入：root = [1,2], p = 1, q = 2
输出：1

提示：

  • 树中节点数目在范围 [2, 105] 内。
  • -109 <= Node.val <= 109
  • 所有 Node.val 互不相同 。
  • p != q
  • p 和 q 均存在于给定的二叉树中。

递归思路

  1. 输入输出：输入node, q, p； 输出公共节点
  2. 终止条件：当前节点为空返回None，当前节点为p或q则返回当前节点
  3. 单层逻辑：需要先搜索左、右子树中是否存在p&q
    1. 如果左、右子树有p&q（即左、右子树不为None），则当前node为公共节点；
    2. 下一步是需要考虑，如何将公共节点传到最上层：这里需要解释下，假设[10,1,7,2,3]（其中2，3为p&q），假设当前节点为10，对10来说，1（左子树）返回值是None（因为不存在p或q），而7（右子树）返回值为7（不为空），说明7就是q&p的最近公共祖先；10只需要将7返回，即if leftNode and not rightNode: return leftNode

image-20250713125002679

递归代码

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
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def foo(self, node, p, q) -> TreeNode:
        # 如果当前节点为空
        # 当前节点为p/q，告诉上层节点，发现了目标值；如果上层节点知道左、右子树都不为空，则上层节点就是公共节点
        if node == q or node == p or not node:
            return node
        
        # 探索左子树是否有p/q
        leftNode = self.foo(node.left, p, q)
        # 探索右子树是否有p/q
        rightNode = self.foo(node.right, p, q)

        # 如果node节点知道左、右子树都不为空，则node节点就是公共节点
        if leftNode and rightNode:
            return node
        
        # 这一步是将已经为公共节点的node，继续向上返回，保证顶部会得到公共节点
        # 这里需要解释下，假设[10,1,7,p,q]，即对10来说，1（左子树）返回值是None，而7（右子树）返回值为7（不为空），说明7就是q&p的最近公共祖先
        # 对10来说，直接返回7就行
        if leftNode and not rightNode:
            return leftNode
        # 同理
        if not leftNode and rightNode:
            return rightNode
        
        return None

    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        return self.foo(root, p, q)

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

https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-search-tree/

给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

例如，给定如下二叉搜索树: root = [6,2,8,0,4,7,9,null,null,3,5]

img

示例 1:

1
2
3
输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
输出: 6 
解释: 节点 2 和节点 8 的最近公共祖先是 6。

示例 2:

1
2
3
输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
输出: 2
解释: 节点 2 和节点 4 的最近公共祖先是 2, 因为根据定义最近公共祖先节点可以为节点本身。

说明:

  • 所有节点的值都是唯一的。
  • p、q 为不同节点且均存在于给定的二叉搜索树中。

递归思路

  1. 本题是BST，可以利用它的特性；如果node大于q.val且大于p.val，则需要向左遍历，在左子树中找公共祖先节点；如果node小于q.val且小于p.val，需要向右遍历，在右子树中找公共祖先节点；否则，直接返回node, node一定为p和q的公共祖先节点

代码

  • 时间复杂度O(N)
  • 空间复杂度O(H)
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
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def foo(self, node, p, q) -> TreeNode:
        if node == q or node == p or not node:
            return node
            
        if node.val > p.val and node.val > q.val:
            # 应该向左子树搜索, 返回左子树的公共节点
            leftNode = self.foo(node.left, p, q)
            # 找到了公共节点就返回
            if leftNode:
                return leftNode

        if node.val < p.val and node.val < q.val:
            rightNode = self.foo(node.right, p, q)
            if rightNode:
                return rightNode
        
        return node

    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        return self.foo(root, p, q)

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

https://leetcode.cn/problems/minimum-absolute-difference-in-bst/

给你一个二叉搜索树的根节点 root ，返回 树中任意两不同节点值之间的最小差值 。

差值是一个正数，其数值等于两值之差的绝对值。

示例 1：

img

1
2
输入：root = [4,2,6,1,3]
输出：1

示例 2：

img

1
2
输入：root = [1,0,48,null,null,12,49]
输出：1

提示：

  • 树中节点的数目范围是 [2, 104]
  • 0 <= Node.val <= 105

迭代思路

  1. 本题和98. 验证二叉搜索树 很像，都可以靠中序遍历，并且判断相邻两位元素的值（差）来解决；这需要用到BST特性，即左节点小于等于root，root小于等于右节点

迭代代码

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
# 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 getMinimumDifference(self, root: Optional[TreeNode]) -> int:
        # 使用中序遍历，记录相邻两位元素差值
        
        if not root:
            return 
        stack = [[root, False]] if root else []
        pre = None
        diff = None
        res = list()
        while stack:
            node, visited = stack.pop()
            if visited:
                if pre:
                    if diff and abs(node.val - pre.val) < diff:
                        diff = abs(node.val - pre.val)
                    if not diff:
                        diff = abs(node.val - pre.val)
                pre = node
            else:
                if node.right:
                    stack.append([node.right, False])
                stack.append([node, True])
                if node.left:
                    stack.append([node.left, False])
                
        return diff

501. 二叉搜索树中的众数

https://leetcode.cn/problems/find-mode-in-binary-search-tree/

给你一个含重复值的二叉搜索树（BST）的根节点 root ，找出并返回 BST 中的所有 众数（即，出现频率最高的元素）。

如果树中有不止一个众数，可以按 任意顺序 返回。

假定 BST 满足如下定义：

  • 结点左子树中所含节点的值 小于等于 当前节点的值
  • 结点右子树中所含节点的值 大于等于 当前节点的值
  • 左子树和右子树都是二叉搜索树

示例 1：

img

1
2
输入：root = [1,null,2,2]
输出：[2]

示例 2：

1
2
输入：root = [0]
输出：[0]

提示：

  • 树中节点的数目在范围 [1, 104] 内
  • -105 <= Node.val <= 105

**进阶：**你可以不使用额外的空间吗？（假设由递归产生的隐式调用栈的开销不被计算在内）

迭代思路

  1. 用中序遍历，关键是在「中间节点的操作」，本题和530二叉搜索树的最小绝对差 以及98. 验证二叉搜索树 相似，需要引入pre节点，判断前后两个元素是否相等，如果相等则将count+1，如果不相等则重置count为1。随后判断count是否等于MaxFreq，如果是，则将元素添加到res里；如果count大于MaxFreq，则将res清空并且将元素添加到res里，并设置MaxFreq等于count
  2. 本题如果只有一个众数，那会相对简直一些，只要一直记录count最大的元素就好，也不用对res清空

迭代代码

  • 时间复杂度O(N)
  • 空间复杂度O(H) – 主要是stack占用的
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
# 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.MostFreq = 1

    def findMode(self, root: Optional[TreeNode]) -> List[int]:
        # 还是按中序遍历，出现频率最高的数可以放在res里，用一个
        stack = list()
        node = root
        pre = None
        res = list()
        count = 1
        while node or stack:
            if node:
                stack.append(node)
                node = node.left
            else:
                # 左
                node = stack.pop()
                
                # 中
                if pre:
                    if pre.val == node.val:
                        count += 1
                    else:
                        count = 1
                pre = node
                if count == self.MostFreq:
                    res.append(node.val)
                    
                elif count > self.MostFreq:
                    res.clear()
                    res.append(node.val)
                    self.MostFreq = count

                # 右
                node = node.right
        return res

递归代码

  • 时间复杂度O(N)
  • 空间复杂度O(H) – 最好O(logN)最坏O(N)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def traverse(self, node) -> List[int]:
    if not node:
        return 
    # 左
    self.traverse(node.left)

    # 中
    if self.pre:
        if self.pre.val == node.val:
            self.count += 1
        else:
            self.count = 1
    self.pre = node
    if self.count == self.MostFreq:
        self.res.append(node.val)
        
    elif self.count > self.MostFreq:
        self.res.clear()
        self.res.append(node.val)
        self.MostFreq = self.count
    
    # 右
    self.traverse(node.right)

思考

如果本题不是BST而是普通树，可以先做遍历（中/前/后/层序都行），再进行排序，排序时按频率将最高频率的添加到res里