Given a binary tree, determine if it is a valid binary search tree (BST).
Assume a BST is defined as follows:
confused what "{1,#,2,3}" means? > read more on how binary tree is serialized on OJ.
Subscribe to see which companies asked this question
用中序遍历依次判断当前节点数值是否比前一个节点大就可以了，注意第一个节点数值判断条件
non-recursion版本
bool isValidBST(TreeNode* root) { if (root == nullptr) return true; stack<TreeNode*> sta; sta.push(root); TreeNode* lastNode = nullptr; TreeNode* lastRoot = root; while (!sta.empty()) { root = sta.top(); if (lastRoot != root->right) { if (lastRoot != root->left) { if (root->left != nullptr) { sta.push(root->left); continue; } } if (!lastNode || root->val > lastNode->val) lastNode = root; else return false; if (root->right != nullptr) { sta.push(root->right); continue; } } lastRoot = root; sta.pop(); } return true; }
原文：http://www.cnblogs.com/sdlwlxf/p/5223590.html