2013.12.31 18:48
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.
confused what "{1,#,2,3}" means?
OJ's Binary Tree Serialization:
The serialization of a binary tree follows a level order traversal, where '#' signifies a path terminator where no node exists below.
Here's an example:
1 / \ 2 3 / 4 \ 5
The above binary tree is serialized as "{1,2,3,#,#,4,#,#,5}".
Solution:
The inorder traversal of a is a sorted array, that's how my code verified the tree.
Perform an inorder traversal and see if the result is sorted. If so, valid; otherwise, no. An extra array is needed to hold the inorder traversal result.
Time complexity and space complexity are both O(n), where n is the number of nodes in a tree.
Accepted code:
1 // 1WA, 1CE, 1AC 2 /** 3 * Definition for binary tree 4 * struct TreeNode { 5 * int val; 6 * TreeNode *left; 7 * TreeNode *right; 8 * TreeNode(int x) : val(x), left(NULL), right(NULL) {} 9 * };10 */11 class Solution {12 public:13 bool isValidBST(TreeNode *root) {14 // IMPORTANT: Please reset any member data you declared, as15 // the same Solution instance will be reused for each test case.16 if(root == nullptr){17 return true;18 }19 arr.clear();20 // 1WA here, the in-order traversal of BST is sorted.21 inorderTraversal(root);22 23 int i, n;24 25 n = arr.size();26 for(i = 0; i < n - 1; ++i){27 if(arr[i] >= arr[i + 1]){28 break;29 }30 }31 arr.clear();32 33 return (i == n - 1);34 }35 private:36 vector arr;37 38 void inorderTraversal(TreeNode *root) {39 // 1CE, null or nullptr...40 if(root == nullptr){41 return;42 }43 44 if(root->left != nullptr){45 inorderTraversal(root->left);46 }47 arr.push_back(root->val);48 if(root->right != nullptr){49 inorderTraversal(root->right);50 }51 }52 };