遍历存在返回值时，如何处理

Question

bobo老师你好，我想问一下 关于leetcode 《653. 两数之和 IV - 输入 BST》 问题
有种解答是这样的

    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);
        return findTarget(root.left, k) || findTarget(root.right, k);
    }

我的问题是：
（1）如果以递归的方式去理解这样的写法，那么这里的宏观语义如何表述？我理解为：在以node为根节点的二叉树中，寻找是否存在两节点之和等于k。
基于这个语义，我对于root的处理方式不太明白。计算出与根节点匹配的节点之后去set中查询，存在即返回true，不存在则去左右子树中查找，将查找结果返回。那么假设root节点是其中一个元素，另一个元素在左右树中。在对root元素处理之后，因为当前set为空，所以返回false，再去左右子树中查找发现也没有发现两个和为k的值，那么最终结果就变成false了，虽然该值已经存在了set中。
（2）如果不借助全局变量的方式去遍历树，如何处理需要返回值的情况，是否只能从对于栈调用的方式去理解？
我的代码借助了一个全局变量记录访问的节点。

class Solution {
    boolean ret = false;
    public boolean findTarget(TreeNode root, int k) {
        Set <Integer> set = new HashSet();
        find(root, k, set);
        return ret;
    }
    public void find(TreeNode root, int k, Set <Integer> set) {
        if (root == null) {
            return;
        }
        find(root.left, k, set);
        //中序遍历
        if(set.contains(k - root.val)) {
            ret = true;
        } else {
            set.add(root.val);
        }
        find(root.right, k, set);
    }
}

Answer 1

liuyubobobo 2020-07-21 18:58:23

1)

宏观语义是：在以 root 为根节点的二叉树中，是否存在一个节点的值，和已经遍历过的某个节点的值，构成了 k。set 中存放的是已经遍历的节点的值。

    public boolean findTarget(TreeNode root, int k) {
        
        if(root == null) {
            return false;
        }   
        
        // 如果在已经遍历的节点的值中，找到了 k - root.val
        // 即和当前 root 的值合在一起构成了 k
        // 返回 true
        if(set.contains(k - root.val)) {
            return true;
        }
        
        // 否则，没有找到，把当前节点的值扔到 set 中，表示遍历了
        set.add(root.val);
        
        // 在 root 的左右子树继续寻找，看有没有节点
        // 和当前已经遍历过的节点，和为 k
        return findTarget(root.left, k) || findTarget(root.right, k);
    }

2)

不使用全局变量可以这样改：

class Solution {
    public boolean findTarget(TreeNode root, int k) {
        Set <Integer> set = new HashSet();
        return find(root, k, set);
    }
    public boolean find(TreeNode root, int k, Set <Integer> set) {
        
        if (root == null) 
            return false;
        
        if(set.contains(k - root.val)) 
            return true;
        
        set.add(root.val);
        
        return find(root.left, k, set) || find(root.right, k, set);
    }
}

继续加油！：）