验证二叉搜索树

问题描述

给定一个二叉树，判断其是否是一个有效的二叉搜索树。
假设一个二叉搜索树具有如下特征：
节点的左子树只包含小于当前节点的数。
节点的右子树只包含大于当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。

示例 1:

输入:
    2
   / \
  1   3
输出: true

示例 2:

输入:
    5
   / \
  1   4
     / \
    3   6
输出: false
解释: 输入为: [5,1,4,null,null,3,6]。
     根节点的值为 5 ，但是其右子节点值为 4 。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/validate-binary-search-tree

思路

将树按中序遍历的顺序存储在vector array中。
令vector tmp=array,将tmp排序，并去重。
去重的目的是判断数的元素是否都严格大于或者小于，因为搜索二叉树中不存在等于的元素。
如果树是搜索二叉树，那么中序遍历得到的数组一定是从大到小排序的。

题解

class Solution {
public:
    vector<int> array;

    bool isValidBST(TreeNode *root) {
        dfs(root);
        vector<int> tmp;
        tmp=array;
        sort(tmp.begin(),tmp.end());
        tmp.erase(unique(tmp.begin(),tmp.end()),tmp.end());
        return tmp == array;
    }

    void dfs(TreeNode *node) {
        if (node == nullptr)return;
        dfs(node->left);
        array.push_back(node->val);
        dfs(node->right);
    }
};