验证二叉搜索树

快来打我* 2022-02-28 14:28 193阅读 0赞

**题目描述**  
给定一个二叉树，判断其是否是一个有效的二叉搜索树。

假设一个二叉搜索树具有如下特征：

节点的左子树只包含小于当前节点的数。  
节点的右子树只包含大于当前节点的数。  
所有左子树和右子树自身必须也是二叉搜索树。

**示例 1:**

输入:
        2
       / \
      1   3
    输出: true

**示例 2:**

输入:
        5
       / \
      1   4
         / \
        3   6
    输出: false
    解释: 输入为: [5,1,4,null,null,3,6]。
         根节点的值为 5 ，但是其右子节点值为 4 。

**解法**  
思路1：二叉搜索树 == 中序遍历结果为升序

/** * 二叉搜索树 == 中序遍历结果为升序 * @param root * @return */
    	public boolean isValidBST(TreeNode root) { 
    		List<Integer> list = new ArrayList<Integer>();
            TreeNode pNode = root;
            LinkedList<TreeNode> stack = new LinkedList<TreeNode>();
            while(pNode!=null || !stack.isEmpty()) { 
            	if(pNode != null) { 
            		stack.push(pNode);
            		pNode = pNode.left;
            	}else { 
    				pNode = stack.pop();
    				list.add(pNode.val);
    				pNode = pNode.right;
    			}
            }
            
            if(list.isEmpty()) { 
            	return true;
            }
            int max = list.get(0);
            for(int i=1;i<list.size();i++) { 
            	if(list.get(i) <= max) { 
            		return false;
            	}else { 
    				max = list.get(i);
    			}
            }
            return true;
        }

对思路1进行优化，不需要List

public boolean isValidBST(TreeNode root) { 
            TreeNode pNode = root;
            LinkedList<TreeNode> stack = new LinkedList<TreeNode>();
            Integer max = null;
            while(pNode!=null || !stack.isEmpty()) { 
            	if(pNode != null) { 
            		stack.push(pNode);
            		pNode = pNode.left;
            	}else { 
    				pNode = stack.pop();
    				if(max !=null && max.intValue()>=pNode.val) { 
    					return false;
    				}
    				max = pNode.val;
    				pNode = pNode.right;
    			}
            }
            
            return true;
        }

继续优化，减少装包、卸包时间

public boolean isValidBST(TreeNode root) { 
            TreeNode pNode = root;
            LinkedList<TreeNode> stack = new LinkedList<TreeNode>();
            long max = Long.MIN_VALUE;
            while(pNode!=null || !stack.isEmpty()) { 
            	if(pNode != null) { 
            		stack.push(pNode);
            		pNode = pNode.left;
            	}else { 
    				pNode = stack.pop();
    				if(max >=pNode.val) { 
    					return false;
    				}
    				max = pNode.val;
    				pNode = pNode.right;
    			}
            }
            
            return true;
        }

思路2：使用递归

/** * 中序遍历：递归法 * @param root * @return */
    long curVal = Long.MIN_VALUE;
        public boolean isValidBST(TreeNode root) { 
    		if(root == null) { 
    			return true;
    		}
    		if(isValidBST(root.left)) { 
    			if(root.val > curVal) { 
    				curVal = root.val;
    				return isValidBST(root.right);
    			}
    		}
    		return false;
    	}