小黑重新站起来看leetcode:653. 两数之和 IV - 输入 BST

小黑答案

# 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: Optional[TreeNode], k: int) -> bool:
        if not root:
            return False
        arr = []
        def pre_tree(node):
            if node:
                arr.append(node.val)
                pre_tree(node.left)
                pre_tree(node.right)
        pre_tree(root)
        for t,i in enumerate(arr):
            if k - i in arr[:t] or k - i in arr[t+1:]:
                return True
        return False

深度优先

# 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: Optional[TreeNode], k: int) -> bool:
        route = set()
        def deep_search(node):
            if not node:
                return False
            
            if k - node.val in route:
                return True
            
            route.add(node.val)

            return deep_search(node.left) or deep_search(node.right)
        return deep_search(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 findTarget(self, root: Optional[TreeNode], k: int) -> bool:
        if not root:
           return False
        route = set()
        q = deque([root])
        while q:
            node = q.popleft()
            if k - node.val in route:
               return True
            route.add(node.val)
            if node.left:
                q.append(node.left)
            if node.right:
                q.append(node.right)
        return False

深度优先搜索 + 中序遍历 + 双指针

# 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: Optional[TreeNode], k: int) -> bool:
        if not root:
            return False
        arr = []
        def mid_display(node):
            if node:
                mid_display(node.left)
                arr.append(node.val)
                mid_display(node.right)
        
        mid_display(root)
        s,e = 0,len(arr) - 1
        while s != e:
            if arr[s]+arr[e] > k:
                e -= 1
            elif arr[s]+arr[e] == k:
                return True
            else:
                s += 1
        return False

迭代+中序遍历

# 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: Optional[TreeNode], k: int) -> bool:
        if not root:
            return False
        left_nodes = [root]
        right_nodes = [root]
        left,right = root,root
        while left.left:
            left = left.left
            left_nodes.append(left)
        while right.right:
            right = right.right
            right_nodes.append(right)

        while right != left:
            sum_ = right.val+left.val
            if sum_ == k:
                return True
            elif sum_ < k:
                left = left_nodes.pop()
                node = left.right
                while node:
                    left_nodes.append(node)
                    node = node.left
                
            else:
                right = right_nodes.pop()
                node = right.left
                while node:
                    right_nodes.append(node)
                    node = node.right
        return False