“This is the 14th day of my participation in the Gwen Challenge in November. Check out the details: The Last Gwen Challenge in 2021.”

Given a binary search treeThe root node rootAnd an integerk, please determine whether there are two nodes in the binary search tree whose sum of values is equal tok. Assume that all nodes in a binary search tree have unique values.

Example 1: input: root = [8,6,10,5,7,9,11], k = 12 output: true description: the sum of nodes 5 and 7 equals 12 example 2: input: Root = [8,6,10,5,7,9,11], k = 22 The number of nodes in the binary tree ranges from [1, 104]. -104 <= node. val <= 104 root is the binary search tree -105 <= k <= 105Copy the code

Source: LeetCode link: leetcode-cn.com/problems/op…

Train of thought

  • When we first see this problem, we think of the original oneLeetCodeThe sum of two numbers of

    • So let’s take a look at LeetCode’s first problem for the idea of adding two numbers

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer,Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            if (map.containsKey(target - nums[i])) {
                return new int[]{map.get(target - nums[i]),i};
            } else{ map.put(nums[i],i); }}return new int[]{};
    }
}
Copy the code
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { public boolean findTarget(TreeNode root, int k) { Set<Integer> set = new HashSet<>(); Stack<TreeNode> stack= new Stack<>(); TreeNode cur = root; while (cur ! = null || ! stack.isEmpty()) { while (cur ! = null) { stack.add(cur); cur = cur.left; } cur = stack.pop(); if (set.contains(k - cur.val)) { return true; } set.add(cur.val); cur = cur.right; } return false; }}Copy the code
  • You can see using an auxiliarymapFor storage

    • So it corresponds to a binary search tree

    • We can go all the way to the left subtree

    • Keep storing the nodes of the left subtree every time you pop them up

    • See if there is a target – val in Set

    Of course, this problem can also play the properties of the binary search tree incisively and vividly, you can regard the binary search tree as a sorted array, and then double pointer operation