LeetCode653. 两数之和 IV - 输入 BST

超、凢脫俗 2022-05-21 09:38 129阅读 0赞

给定一个二叉搜索树和一个目标结果，如果 BST 中存在两个元素且它们的和等于给定的目标结果，则返回 true。

案例 1:

输入: 
        5
       / \
      3   6
     / \   \
    2   4   7
    
    Target = 9
    
    输出: True

案例 2:

输入: 
        5
       / \
      3   6
     / \   \
    2   4   7
    
    Target = 28
    
    输出: False

--------------------

思路：定义一个stack结构用来遍历二叉树，定义一个set结构用来存储遍历过程中目标值（Target）减去当前结点值的值，检查set中的值是否存在二叉树中。

/**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    class Solution {
        public boolean findTarget(TreeNode root, int k) {
            if(null==root) {
        		return false;
        	}
        	ArrayDeque<TreeNode> stack=new ArrayDeque<TreeNode>();  //用来遍历二叉树的stack
        	Set<Integer> set=new HashSet<Integer>();                //用来存储满足二叉树中能够满足k还需的元素值
        	stack.push(root);
        	while(!stack.isEmpty()) {
        		TreeNode node=stack.pop();
        	//	System.out.println(node.val);
        		if(set.contains(node.val)) {
        			return true;
        		}else {
        			set.add(k-node.val);
        		}
        		if(node.right!=null) {
        			stack.push(node.right);
        		}
        		if(node.left!=null) {
        			stack.push(node.left);
        		}
        		
        	}
        	return false;
        }
    }

[更多LeetCode题解案例][LeetCode]

[LeetCode]: https://github.com/yangxuechen/LeetCode-algorithm