首页 > 其他 > 详细

LeetCode 653. Two Sum IV - Input is a BST

时间:2017-12-04 21:46:50      阅读:199      评论:0      收藏:0      [点我收藏+]

Given a Binary Search Tree and a target number, return true if there exist two elements in the BST such that their sum is equal to the given target.

Example 1:

Input: 
    5
   /   3   6
 / \   2   4   7

Target = 9

Output: True

 

Example 2:

Input: 
    5
   /   3   6
 / \   2   4   7

Target = 28

Output: False

题意:给定一棵二叉查找树和一个目标值target,判断BST中是否存在两个元素使其相加和为target
思路:用深度优先搜索,将二叉树中的所有节点值放入ArrayList,然后判断是否存在相加为target的两个元素,实现如下:
public boolean findTarget(TreeNode root, int k) {
        List<Integer> nodes = new ArrayList<>();
        dfs(root, nodes);
        for(int i = 0; i < nodes.size(); i++){
            int val = nodes.get(i);
            if(nodes.contains(k - val) && k - val != val)
                return true;
        }
        return false;
    }
    public void dfs(TreeNode root, List<Integer> nodes){
        if(root != null){
            nodes.add(root.val);
            dfs(root.left, nodes);
            dfs(root.right, nodes);
        }
    }

 

 

LeetCode 653. Two Sum IV - Input is a BST

原文:http://www.cnblogs.com/zeroingToOne/p/7979083.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!