文章目录

• 二叉搜索树
• 1524 · 在二叉搜索树中查找
• 701 · 修剪二叉搜索树
• 算法范式与算法
• • 算法范式
  • 算法
• 分治
• 245 · 子树
• 94 · 二叉树中的最大路径和

二叉搜索树

1524 · 在二叉搜索树中查找

给定一颗二叉搜索树和 value.
返回这棵树中值等于 value 的节点. 如果不存在这样的节点, 返回 null.

一开始左右子树忘记写return了，导致输出为空

def searchBST(self, root, val):
        # Write your code here.
        if not root or root.val == val:
            return root
        if root.val > val:
            return self.searchBST(root.left, val)
        elif root.val < val:
            return self.searchBST(root.right, val)

迭代的写法：

def searchBST(self, root, val):
        # Write your code here.
        while root:
            if root.val == val:
                return root
            if root.val > val:
                root = root.left
            elif root.val < val:
                root = root.right

701 · 修剪二叉搜索树

找到了合适的点位，不知道如何返回，返回什么。

"""
Definition of TreeNode:
class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left, self.right = None, None
"""

class Solution:
    """
    @param root: given BST
    @param minimum: the lower limit
    @param maximum: the upper limit
    @return: the root of the new tree 
    """
    def trimBST(self, root, minimum, maximum):
        # write your code here
        if not root: 
            return
            
        if root.val >= minimum and root.val <= maximum:
            # 两边都要去
            root.left = self.trimBST(root.left, minimum, root.val)
            root.right = self.trimBST(root.right, root.val, maximum)

        elif root.val < minimum:
            # 去右边
            root.right = self.trimBST(root.right, minimum, maximum)

        elif root.val > maximum:
            # 去左边
            root.left = self.trimBST(root.left, minimum, maximum)

看了老师的答案，改的代码：

"""
Definition of TreeNode:
class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left, self.right = None, None
"""

class Solution:
    """
    @param root: given BST
    @param minimum: the lower limit
    @param maximum: the upper limit
    @return: the root of the new tree 
    """
    def trimBST(self, root, minimum, maximum):
        # write your code here
        if not root: 
            return

        if root.val >= minimum and root.val <= maximum:
            # 两边都要去
            root.left = self.trimBST(root.left, minimum, root.val)
            root.right = self.trimBST(root.right, root.val, maximum)
            return root

        elif root.val < minimum:
            # 去右边
            return self.trimBST(root.right, minimum, maximum)

        elif root.val > maximum:
            # 去左边
            return self.trimBST(root.left, minimum, maximum)

算法范式与算法

算法范式

算法

分治

245 · 子树

有两个不同大小的二叉树： T1 有上百万的节点； T2 有好几百的节点。请设计一种算法，判定 T2 是否为 T1的子树。


写的好像很冗长，看下答案：

"""
Definition of TreeNode:
class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left, self.right = None, None
"""

class Solution:
    """
    @param T1: The roots of binary tree T1.
    @param T2: The roots of binary tree T2.
    @return: True if T2 is a subtree of T1, or false.
    """
    def isSubtree(self, T1, T2):
        # write your code here
        if not T1 and not T2:
            return True
        elif not T1 and T2:
            return False
        elif T1 and not T2:
            return True
        

        if self.is_equal(T1, T2):
            return True
        
        return self.isSubtree(T1.left, T2) or self.isSubtree(T1.right, T2)
    
    def is_equal(self, T1, T2):
        if not T1 and not T2:
            return True
        elif not T1 and T2:
            return False
        elif T1 and not T2:
            return False

        if T1.val != T2.val:
            return False

        return self.is_equal(T1.left, T2.left) and self.is_equal(T1.right, T2.right)

官方答案：

class Solution:
    # @param T1, T2: The roots of binary tree.
    # @return: True if T2 is a subtree of T1, or false.
    def get(self, root, rt):
        if root is None:
            rt.append("#")
            return

        rt.append(str(root.val))
        self.get(root.left, rt)
        self.get(root.right, rt)

    def isSubtree(self, T1, T2):
        # write your code here
        rt = []
        self.get(T1, rt)
        t1 = ','.join(rt)

        rt = []
        self.get(T2, rt)
        t2 = ','.join(rt)

        return t1.find(t2) != -1

官方答案和我写的一样

94 · 二叉树中的最大路径和

给出一棵二叉树，寻找一条路径使其路径和最大，路径可以在任一节点中开始和结束（路径和为两个节点之间所在路径上的节点权值之和）

没写出来

def maxPathSum(self, root):
        # write your code here
        max_val = float('-inf')
        max_val = max(max_val, root.val)
        if root.val < 0:
            return 0
        else:
            return root.val

        pathsum = self.maxPathSum(root.left) + self.maxPathSum(root.right) + root.val
        max_val = max(max_val, pathsum)

        curr = max(self.maxPathSum(root.left), self.maxPathSum(root.right)) + root.val

         curr if curr > 0 else 0

下面是看答案修改的代码：

"""
Definition of TreeNode:
class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left, self.right = None, None
"""

class Solution:
    """
    @param root: The root of binary tree.
    @return: An integer
    """

    def maxPathSum(self, root):
        # write your code here
        self.max_val = float('-inf')
        self.get_max_path(root)
        return self.max_val
        

    def get_max_path(self, root):
        if not root:
            return 0

        max_left = self.get_max_path(root.left) 
        max_right = self.get_max_path(root.right)

        self.max_val = max(self.max_val, max_left + max_right + root.val)

        # 以当前点为最高点的最大路径和
        curr = max(max_left, max_right) + root.val

        return curr if curr > 0 else 0