【LeetCode 98】Validate Binary Search (C++)

Problem:

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.

Example 1:

    2
   / \
  1   3

Example 2:

    1
   / \
  2   3

Binary tree [1,2,3], return false.

Solution:

使用中序遍历检测二叉搜索树的有序性，从而达到验证二叉树的效果，其中中序遍历用栈实现

**
 * 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:
    bool isValidBST(TreeNode* root) {
        stack<TreeNode*> s;
        TreeNode* node =root;
        while(node!=NULL){
            s.push(node);
            node=node->left;
        }
        if(!s.empty()){
            TreeNode* cur=s.top();
            s.pop();
            if(cur->right!=NULL){
                s.push(cur->right);
                TreeNode* c=cur->right;
                while(c->left!=NULL){
                    s.push(c->left);
                    c=c->left;
                }
            }
            while(!s.empty()){
                TreeNode* next=s.top();
                s.pop();
                if(cur->val>=next->val)return false;
                TreeNode *n=next;
                if(n->right!=NULL){
                    s.push(n->right);
                    n=n->right;
                    while(n->left!=NULL){
                        s.push(n->left);
                        n=n->left;
                    }
                }
                cur=next;
            }
        }
        return true;
    }
};

Attention:

不能简单的将父亲结点和左右子节点递归比较，因为子节点与父节点的有序关系只是表象，真正的有序是与后继节点的比较，而这可以由中序遍历实现