Offer to come, dig friends take it! I am participating in the 2022 Spring Recruit Punch card activity. Click here for details.

Topic describes

This is the 650 on LeetCode. Only two keys keyboard, easy difficulty.

Tag: “binary tree”, “iteration”, “middle order traversal”, “double pointer”, “hash table”, “tree search”

Given a binary search tree root and a target result k, return true if two elements exist in BST and their sum equals the given target result.

Example 1:

Input: root = [5,3,6,2,4,null,7], k = 9 output: trueCopy the code

Example 2:

Input: root = [5,3,6,2,4,null,7], k = 28 output: falseCopy the code

Tip:

  • The range of nodes in a binary tree is [1,104][1, 10^4][1,104]

  • – 1 0 4   < = N o d e . v a l < = 1 0 4 -10^4 <= Node.val <= 10^4
  • rootIs a binary search tree

  • – 1 0 5   < = k < = 1 0 5 -10^5 <= k <= 10^5

Hash table + tree search

Record the corresponding node values (Set Set is used) during recursive search. If k− X.valk-X.valk − X.val exists in the Set of a node XXX when traversing, it indicates that the sum of two nodes is equal to KKK, and return True. Return False if the entire tree is not searched.

Code:

class Solution {
    Set<Integer> set = new HashSet<>();
    public boolean findTarget(TreeNode root, int k) {
        if (root == null) return false;
        if (set.contains(k - root.val)) return true;
        set.add(root.val);
        returnfindTarget(root.left, k) | findTarget(root.right, k); }}Copy the code
  • Time complexity: O(n)O(n)O(n)
  • Space complexity: O(n)O(n)O(n)

Double pointer + BST in order traversal

Solution 1 does not use the BST property, using the BST sequential traversal order property, we can achieve similar “double pointer” effect.

At this time, the top element of the stack is the minimum and maximum value in BST. L and R are used as pointer proxies respectively. According to the size relationship between the sum of node values pointed to by the two Pointers and KKK, how to make L and R move is guided. The process of moving L is to find the next value greater than L. Val, and the process of moving R is to find the next value smaller than R. val.

Code:

class Solution {
    public boolean findTarget(TreeNode root, int k) {
        Deque<TreeNode> ld = new ArrayDeque<>(), rd = new ArrayDeque<>();
        TreeNode temp = root;
        while(temp ! =null) {
            ld.addLast(temp);
            temp = temp.left;
        }
        temp = root;
        while(temp ! =null) {
            rd.addLast(temp);
            temp = temp.right;
        }
        TreeNode l = ld.peekLast(), r = rd.peekLast();
        while (l.val < r.val) {
            int t = l.val + r.val;
            if (t == k) return true;
            else if (t < k) l = getNext(ld, true);
            else r = getNext(rd, false);
        }
        return false;
    }
    TreeNode getNext(Deque<TreeNode> d, boolean isLeft) {
        TreeNode cur = d.pollLast();
        TreeNode node = isLeft ? cur.right : cur.left;
        while(node ! =null) {
            d.addLast(node);
            node = isLeft ? node.left : node.right;
        }
        returnd.peekLast(); }}Copy the code
  • Time complexity: O(n)O(n)O(n)
  • Space complexity: O(n)O(n)O(n)

The last

This is No.653 of our “Brush through LeetCode” series, which started on 2021/01/01. There are 1916 topics in LeetCode as of the start date, some of which have locks.

In this series of articles, in addition to explaining how to solve the problem, I will also present the most concise code possible. If a general solution is involved, the corresponding code template will also be used.

In order to facilitate the students to debug and submit the code on the computer, I set up the relevant warehouse: github.com/SharingSour… .

In the repository, you’ll see links to the series of articles, the corresponding code for the series of articles, the LeetCode source links, and other preferred solutions.