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

分析：

显而易见，以上算法的时间复杂度为： ​ 。