[LeetCode]653. Two Sum IV - Input is a BST

Description:

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

Solution:

题意：给定给一个二叉搜索树和一个数值target，判断树中是否含有两个元素值相加等于target。

思路：一开始我的思路是用广度优先搜索(BFS)：

1.先将根节点推进队列

2.记录对列头的值flag，依次将其左右子树推进队列，弹出队列头

3.比较target-flag与当前值的大小（第一次当前值与flag相等，跳过），若相等则输出true，否则前者大则进入右子树，后者大则进入左子树

4.循环3直到没有子树

5.循环2直到队列为空

6.输出false

然而我发现有个漏洞：该算法只比较了祖先节点与孩子节点的大小关系，而没有比较兄弟节点的大小关系，那么该算法肯定失败。

后来想到之前做的题目Two Sum II，是用的哈希表存储通过直接搜索来查找元素的，因此，想到可以结合BFS和HASH完成算法：

虽然该算法AC了，但是在编程过程中遇到两个问题：

1.map键-值对中的值没有使用到，是不是可以换一种数据结构节省空间？

2.!q.empty()和q.front() == NULL 为什么不等价，在使用后者语句作为while循环判断条件时产生了访问未申请内存的地址，为什么？

后来通过网上查找资料，加上自己的理解，得到解答：

1.set数据结构

2.即使队列是空的，q.front()表示的应该也是头指针，不为空，因此循环不终止。