day18-binary tree-part06-7.20

tasks for today:

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

2. 501.二叉搜索树中的众数

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

-----------------------------------------------------------------

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

in this practice, the target tree is a binary search tree, which makes it have a special feature that its inorder is an ascending list, so we can first get the inorder list for the binary search tree and then go throught the list recoridng the min_val.

# 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:
        # get inorder list, which get the inscending order list
        result = []
        def inorder_travese(node):
            if not node:
                return None
            
            inorder_travese(node.left)
            result.append(node.val)
            inorder_travese(node.right)
        
        inorder_travese(root)

        min_val = float('inf')
        for i in range(1, len(result)):
            if result[i] - result[i-1] < min_val:
                min_val = result[i] - result[i-1]
        
        return min_val

2. 501.二叉搜索树中的众数 

This practice, a defaultdict can be used to calculate the frequency of the showup for a tree node's value:

# 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 findMode(self, root: Optional[TreeNode]) -> List[int]:
        calcu = collections.defaultdict(int)
        nodeQueue = collections.deque([root])
        while nodeQueue:
            cur = nodeQueue.popleft()
            calcu[cur.val] += 1
            if cur.left:
                nodeQueue.append(cur.left)
            if cur.right:
                nodeQueue.append(cur.right)
        max_num = max(calcu.values())
        result = []
        for key, value in calcu.items():
            if value == max_num:
                result.append(key)
        
        return result

In this practice, the above method is a general solution which works for all types of tress, but if the tree is a not normal binary tree, instead a binary search tree, there is also other solutions which is incented by the binary search tree's feature that the inorder list is an asceding list.

this method use double pointers, similar with 530.

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

this practice is a bit challenging, the tutorial include a summary for sorting when the recursive has return value.

# 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 == p or root == q or root is None:
            return root
        
        left = self.lowestCommonAncestor(root.left, p, q)
        right = self.lowestCommonAncestor(root.right, p, q)

        if left and right: return root
        elif not left and right: return right
        elif left and not right: return left
        else: return None
        

原文地址：https://blog.csdn.net/bbrruunnoo/article/details/140572076

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！