C#LeetCode刷题之#653-两数之和 IV – 输入 BST(Two Sum IV – Input is a BST)

C#LeetCode刷题之#653-两数之和 IV - 输入 BST(Two Sum IV - Input is a BST)

问题

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

输入: 

    5
   / \
  3   6
 / \   \
2   4   7

Target = 9

输出: True

输入: 

    5
   / \
  3   6
 / \   \
2   4   7

Target = 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   7

Target = 9

Output: True

Input: 

   5
   / \
  3   6
 / \   \
2   4   7

Target = 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

分析:

显而易见,以上算法的时间复杂度为: O(n)​ 。

本文由 .Net中文网 原创发布,欢迎大家踊跃转载。

转载请注明本文地址:https://www.byteflying.com/archives/4098

发表评论

登录后才能评论