
问题
给定一个二叉搜索树和一个目标结果,如果 BST 中存在两个元素且它们的和等于给定的目标结果,则返回 true。
输入:
5
/ \
3 6
/ \ \
2 4 7Target = 9
输出: True
输入:
5
/ \
3 6
/ \ \
2 4 7Target = 28
输出: False
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.
Input:
5
/ \
3 6
/ \ \
2 4 7Target = 9
Output: True
Input:
5
/ \
3 6
/ \ \
2 4 7Target = 28
Output: False
示例
public class Program { public static void Main(string[] args) { var root = new TreeNode(1) { left = new TreeNode(3) { left = new TreeNode(5), right = new TreeNode(7) }, right = new TreeNode(9) }; var res = FindTarget(root, 10); Console.WriteLine(res); Console.ReadKey(); } public static bool FindTarget(TreeNode root, int k) { var nums = new List<int>(); PreOrder(root, nums); return TwoSum(nums.ToArray(), k); } public static void PreOrder(TreeNode root, List<int> nums) { if(root == null) return; nums.Add(root.val); PreOrder(root.left, nums); PreOrder(root.right, nums); } public static bool TwoSum(int[] nums, int target) { //用数组中的值做key,索引做value存下所有值 var dictionary = new Dictionary<int, int>(); for(int i = 0; i < nums.Length; i++) { //记录差值 int complement = target - nums[i]; //若字典中已经存在这个值,说明匹配成功 if(dictionary.ContainsKey(complement)) return true; //记录索引 dictionary[nums[i]] = i; } return false; } public class TreeNode { public int val; public TreeNode left; public TreeNode right; public TreeNode(int x) { val = x; } } }
以上给出1种算法实现,以下是这个案例的输出结果:
true
分析:
显而易见,以上算法的时间复杂度为: 。
本文由 .Net中文网 原创发布,欢迎大家踊跃转载。
转载请注明本文地址:https://www.byteflying.com/archives/4098。