二叉树part05

700.二叉搜索树中的搜索：这道题只需要遍历一遍整个二叉树，判断是否有某个结点的值等于我们要搜索的值即可。如果存在这个结点则把找到的结点作为结果返回；如果不存在值等于val的结点，则直接返回null即可。

617.合并二叉树：这道题仍然可以使用迭代的方法，一次性遍历两个二叉树，将每个位置的节点值相加即可。

98.验证二叉搜索树：这道题需要用到二叉搜索树的特性。通过对二叉搜索树进行中序遍历得到的结果，应该就是从小到大的数字排列。利用这一特性，只需要对二叉搜索树执行一次中序遍历，并将遍历得到的结果进行检查。判断是否是从小到大的即可。这道题存在巨大的陷阱：绝对不能单纯的判断某个节点的左右叶子节点，是不是满足左孩子节点小于根节点，右孩子节点大于根节点。因为仅仅满足这一点，可能不是一个二叉搜索树。左右孩子节点和其父节点的父节点间的大小关系无法判断，这就可能导致判断的结果出错。如下图所示：

而真正需要比较的是：左子树的所有节点小于中间节点，右子树的所有节点大于中间节点。

这道题要学会二叉搜索树的特性！