Leetcode题解-数据结构-树(BST)（python版）

迈不过友情╰ 2022-11-04 14:22 167阅读 0赞

### 文章目录 ###

*   *  1、修剪二叉查找树
     *  2、二叉查找树的第 k 个元素
     *  3、把二叉查找树每个节点的值都加上比它大的节点的值
     *  4、二叉查找树的最近公共祖先
     *  5、二叉树的最近公共祖先
     *  6、 有序数组构造二叉查找树
     *  7、 有序链表构造二叉查找树
     *  8、寻找两个点，和为给定值
     *  9、二叉搜索树中两节点差的最小值
     *  10、寻找二叉查找树中出现次数最多的值

## 1、修剪二叉查找树 ##

[669. 修剪二叉搜索树(Medium)][669. _Medium]

# 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 trimBST(self, root: TreeNode, low: int, high: int) -> TreeNode:
            if root == None:
                return None
            if root.val < low: return self.trimBST(root.right, low, high)
            if 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

## 2、二叉查找树的第 k 个元素 ##

[230. 二叉搜索树中第K小的元素(Medium)][230. _K_Medium]

要思想是中序遍历，遍历到第 k 个元素的时候，将这个元素保留下来。

递归

迭代

# 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 kthSmallest(self, root: TreeNode, k: int) -> int:
            count = 0
            res = root.val
            stack = []
            p = root
            while(stack or p):
                while p:
                    stack.append(p)
                    p = p.left
                if stack:
                    p = stack.pop()
                    count += 1
                    if count == k:
                        res = p.val
                        break
                    p = p.right
    
            return res

## 3、把二叉查找树每个节点的值都加上比它大的节点的值 ##

[538. 把二叉搜索树转换为累加树(Medium)][538. _Medium]  
遍历，先遍历右子树，再根节点，最后左子树

递归：

# 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 convertBST(self, root: TreeNode) -> TreeNode:
            sum = 0
            def last(root):
                nonlocal sum
                if root == None:
                    return root
                if root.right:
                    last(root.right)
                sum += root.val
                root.val = sum
                if root.left:
                    last(root.left)
            last(root)
            return root

迭代

# 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 convertBST(self, root: TreeNode) -> TreeNode:
            sum = 0
            stack = []
            p = root
            while stack or p:
                while p:
                    stack.append(p)
                    p = p.right
                if stack:
                    p = stack.pop()
                    sum += p.val
                    p.val = sum
                    p = p.left
            return root

## 4、二叉查找树的最近公共祖先 ##

[235. 二叉搜索树的最近公共祖先(Easy)][235. _Easy]  
**方法一**：递归

# Definition for a binary tree node.
    # class TreeNode:
    #     def __init__(self, x):
    #         self.val = x
    #         self.left = None
    #         self.right = None
    
    class Solution:
        def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
            if p.val > q.val:
                p, q = q, p
            if p.val <= root.val <= q.val:
                return root
            if root.val < p.val:
                return self.lowestCommonAncestor(root.right, p, q)
            if root.val > q.val:
                return self.lowestCommonAncestor(root.left, p, q)

**方法二**：求取从根节点到 p, q 的路径，再取交集

得到从根节点到 p 和 q 的路径，最后一个相同的节点就是公共祖先

# Definition for a binary tree node.
    # class TreeNode:
    #     def __init__(self, x):
    #         self.val = x
    #         self.left = None
    #         self.right = None
    
    class Solution:
        def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
            def get_path(root, target):
                node = root
                path_list = list()
                while (node != target):
                    path_list.append(node)
                    if node.val < target.val:
                        node = node.right
                    elif node.val > target.val:
                        node = node.left
                path_list.append(node)
                return path_list
    
            path_p = get_path(root, p)
            path_q = get_path(root, q)
            parent = None
            for u, v in zip(path_p, path_q):
                if u == v:
                    parent = u
                else:
                    break
            return parent

时间复杂度：O(n)  
空间复杂度：O(n)

**方法三**： 一次遍历

将这两个节点放在一起遍历。从根节点开始遍历；

*  如果当前节点的值大于 p 和 q 的值，说明 p 和 q 应该在当前节点的左子树，因此将当前节点移动到它的左子节点；
 *  如果当前节点的值小于 p 和 q 的值，说明 pp 和 qq 应该在当前节点的右子树，因此将当前节点移动到它的右子节点；
 *  如果当不满足上述两条要求，则当前节点是分岔点。此时，p 和 q 要么在当前节点的不同的子树中，要么其中一个就是当前节点。

# Definition for a binary tree node.
    # class TreeNode(object):
    #     def __init__(self, x):
    #         self.val = x
    #         self.left = None
    #         self.right = None
    
    class Solution(object):
        def lowestCommonAncestor(self, root, p, q):
            if p.val > q.val:
                p, q = q, p
            node = root
            while (True):
                if node.val < p.val:
                    node = node.right
                elif node.val > q.val:
                    node = node.left
                else:
                    break
            return node

时间复杂度：O(n)  
空间复杂度：O(1)

## 5、二叉树的最近公共祖先 ##

[236. 二叉树的最近公共祖先(Medium)][236. _Medium]

解题思路：  
用递归解决，问题分解为查看子树中是否存在结点p或者q。从根节点开始遍历，循环终止条件为结点p和q中的任一个和root匹配。分别递归左、右子树，查看左右子树中是否有结点p或者q，如果两个结点分别存在左右子树中，root就是公共结点，如果两个节点都出现在左子树，则说明最近公共祖先在左子树中，否则在右子树。

# Definition for a binary tree node.
    # class TreeNode:
    #     def __init__(self, x):
    #         self.val = x
    #         self.left = None
    #         self.right = None
    
    class Solution:
        def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
            if root == None or root == p or root == q:
                return root
            left = self.lowestCommonAncestor(root.left, p, q)
            right = self.lowestCommonAncestor(root.right, p, q)
            if left != None and right != None:
                return root
            if left:
                return left
            return right

## 6、 有序数组构造二叉查找树 ##

[108. 将有序数组转换为二叉搜索树(Easy)][108. _Easy]

解题思路：每次将数组中间的那个元素作为根节点，将剩下的元素分为两个区间，分别构造根节点的左子树和右子树

# 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 sortedArrayToBST(self, nums: List[int]) -> TreeNode:
            n = len(nums)
            if n == 0:
                return None
            if n == 1:
                return TreeNode(nums[0])
            mid = n//2
            root = TreeNode(nums[mid])
            root.left = self.sortedArrayToBST(nums[:mid])
            root.right = self.sortedArrayToBST(nums[mid+1:])
            return root

## 7、 有序链表构造二叉查找树 ##

[109. 有序链表转换二叉搜索树(Medium)][109. _Medium]

设当前链表的左端点编号为 left，右端点编号为 right，包含关系为双闭，中序遍历的顺序是 左子树 - 根节点 - 右子树，在分治的过程中，我们不用急着找出链表的中位数节点，而是使用一个占位节点，等到中序遍历到该节点时，再填充它的值。

我们可以通过计算编号范围来进行中序遍历：

*  中位数节点对应的编号为 mid = (left+right+1)/2；
 *  左右子树对应的编号范围分别为 \[left, mid−1\] 和 \[mid+1, right\]

如果 left>right，那么遍历到的位置对应着一个空节点，否则对应着二叉搜索树中的一个节点。

# Definition for singly-linked list.
    # class ListNode:
    #     def __init__(self, val=0, next=None):
    #         self.val = val
    #         self.next = next
    # 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 sortedListToBST(self, head: ListNode) -> TreeNode:
            def size(head):
                n = 0
                node = head
                while (node):
                    n += 1
                    node = node.next
                return n
    
            def convert(l, r):
                nonlocal cur
                if l > r: return None
                mid = (l + r + 1) // 2
                left = convert(l, mid-1)
                node = TreeNode(cur.val)
                node.left = left
                cur = cur.next
                node.right = convert(mid + 1, r)
                return node
    
            list_len = size(head)
            cur = head
            return convert(0, list_len - 1)

时间复杂度：O(n)，n 是链表的长度。

设长度为 nn 的链表构造二叉搜索树的时间为 T(n)T(n)，递推式为 T(n) = 2 \\cdot T(n/2) + O(1)T(n)=2⋅T(n/2)+O(1)，根据主定理，T(n) = O(n)T(n)=O(n)。

空间复杂度：O(\\log n)O(logn)，这里只计算除了返回答案之外的空间。平衡二叉树的高度为 O(\\log n)O(logn)，即为递归过程中栈的最大深度，也就是需要的空间。

作者：LeetCode-Solution  
链接：https://leetcode-cn.com/problems/convert-sorted-list-to-binary-search-tree/solution/you-xu-lian-biao-zhuan-huan-er-cha-sou-suo-shu-1-3/  
来源：力扣（LeetCode）  
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

## 8、寻找两个点，和为给定值 ##

[653. 两数之和 IV - 输入 BST(Easy)][653. _ IV - _ BST_Easy]

解题思路：用中序遍历将二叉树的值，有序的放到数组中，再用双指针寻找和为给定值的节点是否存在。

# 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 findTarget(self, root: TreeNode, k: int) -> bool:
            val_sorted = []
            def mid_view(root):
                nonlocal val_sorted
                if root == None:
                    return
                if root.left:
                    mid_view(root.left)
                val_sorted.append(root.val)
                if root.right:
                    mid_view(root.right)
            mid_view(root)
            if val_sorted[0]*2 > k or val_sorted[-1]*2 < k:
                return False
            n = len(val_sorted)
            left = 0
            right = n-1
            while(left < right):
                if val_sorted[left] + val_sorted[right] == k:
                    return True
                elif val_sorted[left] + val_sorted[right] > k:
                    right -= 1
                else:
                    left += 1
            return False

## 9、二叉搜索树中两节点差的最小值 ##

[530. 二叉搜索树的最小绝对差(Easy)][530. _Easy]

解题思路：中序遍历，求解两相邻节点差的最小值，每次保留上一次访问的节点，本次节点值减去上次节点值，差的最小值

# Definition for a binary tree node.
    # class TreeNode:
    #     def __init__(self, x):
    #         self.val = x
    #         self.left = None
    #         self.right = None
    
    class Solution:
        def getMinimumDifference(self, root: TreeNode) -> int:
            pre = None
            res = float('inf')
    
            def mid_view(root):
                nonlocal pre
                nonlocal res
                if root == None: return
                if root.left: mid_view(root.left)
                if pre: res = min(res, root.val-pre.val)
                pre = root
                if root.right: mid_view(root.right)
            
            mid_view(root)
            return res

## 10、寻找二叉查找树中出现次数最多的值 ##

解题思路：

遍历，将元素放入数组，使用 collections.Counter().most\_common() 统计元素出现的频率，再按照频率从高到低排序，取出前面频率相同的元素

# Definition for a binary tree node.
    # class TreeNode:
    #     def __init__(self, x):
    #         self.val = x
    #         self.left = None
    #         self.right = None
    
    class Solution:
        def findMode(self, root: TreeNode) -> List[int]:
            val_sort = []
            if root == None:
                return []
            
            def mid(root):
                nonlocal val_sort
                if root == None:
                    return
                if root.left: mid(root.left)
                val_sort.append(root.val)
                if root.right: mid(root.right)
            
            mid(root)
            d = collections.Counter(val_sort).most_common()
    
            n = len(d)
            res = [d[0][0]]
            for i in range(n-1):
                if d[i][1] == d[i+1][1]:
                    res.append(d[i+1][0])
                else:
                    break
    
            return res

采用中序遍历，从小到大访问二叉搜索树中的元素，记录上一个不一样的元素大小，记录当前元素大小，当前元素大小变化时，查看元素出现的个数，如果大于前面的记录，清空记录并更新，如果个数相等，将该元素也加入。

# Definition for a binary tree node.
    # class TreeNode:
    #     def __init__(self, x):
    #         self.val = x
    #         self.left = None
    #         self.right = None
    
    class Solution:
        def findMode(self, root: TreeNode) -> List[int]:
            res = []
            if root == None: return []
            base = root.val
            count = 0
            maxcount = 0
    
            def update(x):
                nonlocal res, base, count, maxcount
                if x == base:
                    count += 1
                else:
                    count = 1
                    base = x
                if count == maxcount:
                    res.append(x)
                if count > maxcount:
                    maxcount = count
                    res = [x]
    
            def mid(root):
                if root == None: return
                if root.left: mid(root.left)
                update(root.val)
                if root.right: mid(root.right)
            
            mid(root)
            return res

[669. _Medium]: https://leetcode-cn.com/problems/trim-a-binary-search-tree/
[230. _K_Medium]: https://leetcode-cn.com/problems/kth-smallest-element-in-a-bst/
[538. _Medium]: https://leetcode-cn.com/problems/convert-bst-to-greater-tree/
[235. _Easy]: https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-search-tree/
[236. _Medium]: https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree/
[108. _Easy]: https://leetcode-cn.com/problems/convert-sorted-array-to-binary-search-tree/
[109. _Medium]: https://leetcode-cn.com/problems/convert-sorted-list-to-binary-search-tree/
[653. _ IV - _ BST_Easy]: https://leetcode-cn.com/problems/two-sum-iv-input-is-a-bst/
[530. _Easy]: https://leetcode-cn.com/problems/minimum-absolute-difference-in-bst/