98. Validate Binary Search Tree

发布时间：2020-12-14 04:35:29 所属栏目：大数据来源：网络整理

导读：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 node

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:

Input:
    2
   /   1   3
Output: true

Example 2:

    5
   /   1   4
?    / ?   3   6
Output: false
Explanation: The input is: [5,1,4,null,3,6]. The root node‘s value
?            is 5 but its right child‘s value is 4.


验证一棵树是否为二叉搜索树

java：

 1 /**
 2  * Definition for a binary tree node.
 3  * public class TreeNode {
 4  *     int val;
 5  *     TreeNode left;
 6  *     TreeNode right;
 7  *     TreeNode(int x) { val = x; }
 8  * }
 9  */
10 class Solution {
11     public boolean isValidBST(TreeNode root) {
12         if (root == null)
13             return true ;
14         Stack<TreeNode> stack = new Stack<TreeNode>() ;
15         TreeNode cur = root ;
16         TreeNode pre = null ;
17         boolean flag = true ;
18         while(cur != null || !stack.isEmpty()){
19             while(cur != null){
20                 stack.push(cur) ;
21                 cur = cur.left ;
22             }
23             TreeNode node = stack.pop() ;
24             if (pre != null && node.val <= pre.val){
25                 flag = false ;
26                 break ;
27             }
28             pre = node ;
29             cur = node.right ;
30         }
31         return flag ;
32     }
33 }

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!