Sword finger offer II 056. Sum of two nodes in a binary search tree (simple binary search tree DFS hash table double pointer iterator)

The finger of the sword Offer II 056. The sum of two nodes in a binary search tree

Given a binary search tree The root node root And an integer k , Please judge whether there are two nodes in the binary search tree, and the sum of their values is equal to k . Suppose that the values of nodes in the binary search tree are unique .

Example 1：

Input : root = [8,6,10,5,7,9,11], k = 12
Output : true
explain : node 5 And nodes 7 The sum is equal to 12
Example 2：

Input : root = [8,6,10,5,7,9,11], k = 22
Output : false
explain : There are no two nodes. The sum of the values is 22 The node of

Tips ：

The range of the number of nodes in a binary tree is [1, 104].
-104 <= Node.val <= 104
root For binary search tree
-105 <= k <= 105

source ： Power button （LeetCode）
link ：https://leetcode-cn.com/problems/opLdQZ
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

analysis

Method 1 ：dfs + Hashtable （ Spatial complexity O(n)）
Directly traverse the storage node value to find whether there are two numbers that meet the conditions .
Method 2 ： iterator + Double pointer （ Spatial complexity O(h）
h It's the depth of the tree . Refer to the first 6 The train of thought of the question and the 55 Iterator of question ：
https://blog.csdn.net/weixin_43942435/article/details/122953885
https://blog.csdn.net/weixin_43942435/article/details/124128125
Treat the binary search tree as an array , Create two opposite iterators , So there are two pointers , Refer to the first 6 The train of thought of the question can be .

Answer key （Java）

Method 1 ：dfs + Hashtable

/** * 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 {
    
    private 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);
        boolean left = findTarget(root.left, k);
        boolean right = findTarget(root.right, k);
        return left || right;
    }
}

Method 2 ： iterator + Double pointer

/** * 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) {
    
        if (root == null) {
    
            return false;
        }

        BSTIterator iterNext = new BSTIterator(root);
        BSTIteratorReversed iterPrev = new BSTIteratorReversed(root);

        int next = iterNext.next();
        int prev = iterPrev.prev();
        while (next != prev) {
    
            if (next + prev == k) {
    
                return true;
            }

            if (next + prev < k) {
    
                next = iterNext.next();
            } else {
    
                prev = iterPrev.prev();
            }
        }

        return false;
    }

    public class BSTIterator {
    
        private TreeNode root;
        private Deque<TreeNode> stack;
        
        public BSTIterator(TreeNode root) {
    
            this.root = root;
            stack = new LinkedList<>();
        }
        
        public int next() {
    
            while (root != null) {
    
                stack.push(root);
                root = root.left;
            }

            root = stack.pop();
            int val = root.val;
            root = root.right;

            return val;
        }
        
        public boolean hasNext() {
    
            return root != null || !stack.isEmpty();
        }
    }

    public class BSTIteratorReversed {
    
        private TreeNode root;
        private Deque<TreeNode> stack;
        
        public BSTIteratorReversed(TreeNode root) {
    
            this.root = root;
            stack = new LinkedList<>();
        }
        
        public int prev() {
    
            while (root != null) {
    
                stack.push(root);
                root = root.right;
            }

            root = stack.pop();
            int val = root.val;
            root = root.left;

            return val;
        }
        
        public boolean hasPrev() {
    
            return root != null || !stack.isEmpty();
        }
    }
}