Validate Binary Search Tree--判断一个树是不是二叉查找树（重重重）-白红宇

Validate Binary Search Tree--判断一个树是不是二叉查找树（重重重）

阅读量：4109 次

发布时间：2019-05-25

本文共 1735 字，大约阅读时间需要 5 分钟。

问题：

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?

解答：

根据二叉查找树的定义：

结点node的左子树所有结点的值都小于node的值。

结点node的右子树所有结点的值都大于node的值。

结点node的左右子树同样都必须是二叉搜索树。

采用递归判断，在判断一个二叉树是否是二叉查找树的同时，需要返回该二叉查找树的最大和最小值，用于父节点判断。

参考：在判断一个树是否是平衡二叉树时返回二叉树的深度。（）

如果该节点为空那么直接返回 true。

如果该节点是叶子节点，返回 true, 该树的最大值和最小值都是node->val.

如果该节点的两个左右子树都是二叉查找树。

{

如果左子树为空，同时节点值小于右子树最小值。是二叉查找树，更新Max = rightmax , min = node->val;

如果右子树为空，同时节点值大于左子树最大值。是二叉查找树，更新max = node->val, min = leftmin;

如果左右子树都不为空，同时节点值大于左子树最大值，小于右子树最小值，是二叉树。更新max = rightmax, min = leftmin;

}

另外的几种解法：

还有一种中序遍历法没看懂，再看。

代码：

class Solution {public:    bool isValidBST(TreeNode *root) {        int max, min;		return isBST(root, max, min);    }	bool isBST(TreeNode *node, int &max, int &min)	{		int leftmax;		int leftmin;		int rightmax;		int rightmin;		if(node == NULL)			return true;		if(node->left == NULL && node->right == NULL)		{			max = node->val;			min = node->val;			return true;		}		else if(isBST(node->left, leftmax, leftmin) && isBST(node->right, rightmax, rightmin))		{			if(node->left == NULL && node->val < rightmin)			{				max = rightmax;				min = node->val;				return true;			}			else if(node->right == NULL && node->val > leftmax)			{				max = node->val;				min = leftmin;				return true;			}			else if(leftmax < node->val && node->val < rightmin)			{				max = rightmax;				min = leftmin;				return true;			}						return false;		}		else		{			return false;		}	}};

转载地址：http://gktsi.baihongyu.com/

你可能感兴趣的文章