Leetcode 98. Validate Binary Se

原题地址：https://leetcode.com/problems/validate-binary-search-tree/description/

题目描述

Given a binary tree, determine if it is a valid binary search tree (BST).
Assume a BST is defined as follows:

• The left subtree of a node contains only nodes with keys less than the node's key.
• The right subtree of a node contains only nodes with keys greater than the node's key.
• Both the left and right subtrees must also be binary search trees.

例子就不贴了。就是要判断一棵二叉树是不是有效的搜索树，即左子节点的值小于父节点的值，右子节点的值大于父节点的值。

思路

一开始我写了一个DFS，在遍历的时候检查每单个父节点和它的两个子节点的大小关系，但是即便每个父节点都符合这样的检查条件仍然可能是无效的搜索树，如图

失败样例.png

元素6这个节点就不该出现在右边的子树上，因为6小于10。
之后我的做法是，对符合题目条件的有效搜索树进行中序遍历，判断所得到的数组是不是已经有序了（递增）。如果是则返回true，不是则返回false。

代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> result;
    void travelInorder(TreeNode* root){
        if(root!=NULL){
            travelInorder(root->left);
            result.push_back(root->val);
            travelInorder(root->right);
        }
    }
    
    bool isValidBST(TreeNode* root) {
        if(root==NULL){
            return true;
        }
        travelInorder(root);
        for(int i =0 ;i<result.size()-1;i++){
            if(result[i]>=result[i+1]){
                return false;
            }
        }
        return true;
    }
};

运行时间击败了%39.21的人。

踩坑

要注意的地方就是出现相等的元素算无效搜索树，以及输入可能为空。