如果找到一个二叉树是一个二叉搜索树 [英] Finding if a Binary Tree is a Binary Search Tree

问题描述

今天，我有一个采访，我被要求写一个程序，它接受一个二叉树，并返回true，如果它也是一个二叉搜索树，否则为false。

Today I had an interview where I was asked to write a program which takes a Binary Tree and returns true if it is also a Binary Search Tree otherwise false.

我的Approach1：执行inroder遍历和存储元件O（n）时间。现在通过元素的数组/列表扫描和我检查元素^日指数大于元素在第（i + 1）^日指数。如果遇到这种情况，返回false，打破循环。 （这需要O（n）的时间）。在结束返回true。

My Approach1: Perform an inroder traversal and store the elements in O(n) time. Now scan through the array/list of elements and check if element at i^th index is greater than element at (i+1)^th index. If such a condition is encountered, return false and break out of the loop. (This takes O(n) time). At the end return true.

不过，这位先生要我提供了一个有效的解决方案。我试过，但我是unsuccessfult，因为发现如果它是一个BST我要检查每一个节点。

But this gentleman wanted me to provide an efficient solution. I tried but I was unsuccessfult, because to find if it is a BST I have to check each node.

此外，他指着我考虑recusrion。 我的方法2：BT是一个BST如果任何节点N N->左侧为＆lt; N和N->右键> N，和N个左节点的序后继小于N和N个右节点的序后继大于N和左，右子树是BSTS。

Moreover he was pointing me to think over recusrion. My Approach 2: A BT is a BST if for any node N N->left is < N and N->right > N , and the INorder successor of left node of N is less than N and the inorder successor of right node of N is greater than N and the left and right subtrees are BSTs.

但是，这将是复杂，运行时间似乎并不好。请帮助，如果你知道任何最优的解决方案。

But this is going to be complicated and running time doesn't seem to be good. Please help if you know any optimal solution.

感谢。

推荐答案

这是一个pretty的众所周知的问题有如下回答：

It's a pretty well-known problem with the following answer:

public boolean isValid(Node root) {
     return isValidBST(root, Integer.MIN_VALUE,
          Integer.MAX_VALUE);
}
private boolean isValidBST(Node node, int MIN, int MAX) {
     if(node == null)
         return true;
     if(node.value > MIN 
         && node.value < MAX
         && isValidBST(node.left, MIN, Math.min(node.value,MAX))
         && isValidBST(node.right, Math.max(node.value,MIN), MAX))
         return true;
     else 
         return false;
}

递归调用可以确保子树的节点是其祖先的范围，这是很重要的范围内。运行时间复杂度将是O（n）的，因为每个节点都检查一次。

The recursive call makes sure that subtree nodes are within the range of its ancestors, which is important. The running time complexity will be O(n) since every node is examined once.

其他的解决办法是做一个序遍历，并检查顺序排序，特别是因为你已经知道，一个二叉树作为输入。

The other solution would be to do an inorder traversal and check if the sequence is sorted, especially since you already know that a binary tree is provided as an input.

这篇关于如果找到一个二叉树是一个二叉搜索树的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！