Shulou(Shulou.com)06/02 Report--

The editor will share with you the example analysis of Validate Binary Search Tree. I hope you will get something after reading this article. Let's discuss it together.

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.

Solution 1:

Recursive idea, recursive preorder traversal, assuming that the current node is root, the lower right corner node of the left subtree is pre, and the lower left corner node of the right subtree is next.

Case 1: root==NULL,return true

Case 2:

If the rootkeeper is null, it is judged that

A) if there is a left child, return false if root- > left- > val > = root- > val

B) if it is smaller than the element in the lower right corner of the left subtree, return false

C) if there is a right child, that is, if root- > right- > valval, return false

D) if it is larger than the lower left corner of the right subtree, that is, if next- > valval,return false

If the value of the current node is larger than that of the left child, smaller than that of the right child, and smaller than that of the subsequent node, the results of the left subtree and the right subtree are returned.

That is,

Finally, return BST (root- > left) & & BST (root- > right)

TreeNode* findpre (TreeNode* root) {if (! root | |! root- > left) return NULL; TreeNode* paired root-> left; while (p-> right) {pumped-> right;} return p;} TreeNode* findnext (TreeNode* root) {if (! root | |! root- > right) return NULL; TreeNode* paired root-> right While (p-> left) {pamphp-> left;} return p;} bool isValidBST (TreeNode* root) {if (! root) return true; if (root- > left&&root- > left- > val > = root- > val) return false; if (root- > right&&root- > right- > valval) return false TreeNode * pre=findpre (root), * next=findnext (root); if (pre&&pre- > val > = root- > val | | next&&next- > valval) return false; return isValidBST (root- > left) & & isValidBST (root- > right);}

Solution 2:

From the solution, we can see that, in fact, as long as the current value is larger than the pre node of the left subtree, and the value of the next node of the right subtree is smaller than that of the right subtree, you can comment out the two cases, but there is also a certain usefulness, you can first judge the left and right children, if the left and right children are not satisfied, then you don't have to look for preorder and succession.

Bool isValidBST (TreeNode* root) {if (! root) return true; / * if (root- > left&&root- > left- > val > = root- > val) return false; if (root- > right&&root- > right- > valval) return false;*/ TreeNode* pre=findpre (root), * next=findnext (root); if (pre&&pre- > val > = root- > val | next&&next- > valval) return false Return isValidBST (root- > left) & & isValidBST (root- > right);}

Solution 3:

In fact, the ordered sequence can be obtained by traversing the middle order, as long as the current node is larger than the previous node, that is, BST.

Bool isValidBSTCore (TreeNode * root,TreeNode * & pre) {if (! root) return true; if (! isValidBSTCore (root- > left,pre)) / / left subtree return false; if (pre&&pre- > val > = root- > val) / / compared with the previous node, return false; pre=root;// modifies pre return isValidBSTCore (root- > right,pre) / / right subtree} bool isValidBST (TreeNode* root) {if (! root) return true; TreeNode* pre=NULL; return isValidBSTCore (root,pre);} after reading this article, I believe you have some understanding of "sample Analysis of Validate Binary Search Tree". If you want to know more about it, welcome to follow the industry information channel, thank you for reading!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.