Leetcode 面试题 04.05. 合法二叉搜索树

爱被打了一巴掌 2023-03-14 08:03 2阅读 0赞

### Leetcode 面试题 04.05. 合法二叉搜索树 ###

*  1、问题分析
 *  2、问题解决
 *  3、总结

# 1、问题分析 #

本质上就是一个二叉树的遍历问题，但是需要注意的是根节点要比左子节点都大，而且比右子节点都小，有一个不满足就失败。

# 2、问题解决 #

笔者以C++方式解决。

#include "iostream"
    
    using namespace std;
    
    #include "algorithm"
    #include "vector"
    #include "math.h"
    
    struct TreeNode { 
    	int val;
    	TreeNode *left;
    	TreeNode *right;
    
    	TreeNode(int x) : val(x), left(NULL), right(NULL) { 
    
    	}
    };
    
    class Solution { 
    public:
    	bool isValidBST(TreeNode *root) { 
    		// 如果根节点为空，则直接返回true
    		if (root == NULL) { 
    			return true;
    		}
    
    		// 和左子树比较，如果左子树有节点比根节点大，则直接返回false
    		if (!compareWithLeftTree(root->left, root->val)) { 
    			return false;
    		}
    		// 和右子树比较，如果右子树有节点比根节点小，则直接返回false
    		if (!compareWithRightTree(root->right, root->val)) { 
    			return false;
    		}
    
    		// 如果根节点符合条件，则遍历左子节点和右子节点
    		return isValidBST(root->left) && isValidBST(root->right);
    	}
    
    	/** * 判断左子树是否比全部比根节点小(本质上就是二叉树的遍历，这里使用的是先序遍历) * @param root * @param val * @return */
    	bool compareWithLeftTree(TreeNode *root, int val) { 
    		// 如果根节点为空，则直接返回true
    		if (root == NULL) { 
    			return true;
    		}
    
    		// 如果该节点的值大于根节点，直接返回false
    		if (root->val >= val) { 
    			return false;
    		}
    		// 递归遍历左子节点
    		if (!compareWithLeftTree(root->left, val)) return false;
    		// 递归遍历右子节点
    		return compareWithLeftTree(root->right, val);
    	}
    
    	/** * 判断右子树是否比都比根节点大(这里的逻辑和左子树的相反，但是思想类似) * @param root * @param val * @return */
    	bool compareWithRightTree(TreeNode *root, int val) { 
    		// 如果根节点为空，则直接返回true
    		if (root == NULL) { 
    			return true;
    		}
    
    		// 如果该节点的值小于根节点，直接返回false
    		if (root->val <= val) { 
    			return false;
    		}
    		// 递归遍历左子节点
    		if (!compareWithRightTree(root->left, val)) return false;
    		// 递归遍历右子节点
    		return compareWithRightTree(root->right, val);
    	}
    };
    
    /** * 先序遍历 * @param root */
    void preorder(TreeNode *root) { 
    	if (root == NULL || root->val == -1) { 
    		return;
    	}
    	// 先访问根节点
    	cout << root->val << endl;
    	// 再访问左子节点
    	preorder(root->left);
    	// 最后访问右子节点
    	preorder(root->right);
    }
    
    /** * 根据数组创建二叉树 * @param a * @param n * @return */
    TreeNode *create(int a[], int n) { 
    	// 根据数组大小分配内存空间
    	TreeNode *ptree = (TreeNode *)malloc(sizeof(TreeNode) * n);
    	int i;
    	// 根据数组的值，依次给二叉树节点赋值
    	for (i = 0; i < n; i++) { 
    		// if (a[i] == -1) { 
    		// ptree[i] = NULL;
    		// continue;
    		// }
    		ptree[i].val = a[i];//数组a只起到一个赋值的作用
    		ptree[i].left = NULL;
    		ptree[i].right = NULL;
    	}
    	// 将数组中节点按照二叉树规则连接起来
    	for (i = 0; i <= n / 2 - 1; i++)//原来的父亲节点范围为1~n/2,现在0~n/2-1,所以注意n/2要取到等
    	{ 
    		if (2 * i + 1 <= n - 1)
    			ptree[i].left = &ptree[2 * i + 1];//把第2*i+1个结点的地址赋给左孩子
    		if (2 * i + 2 <= n - 1)
    			ptree[i].right = &ptree[2 * i + 2];
    	}
    	return ptree;
    }
    
    template<class T>
    
    /** * 获取数组长度 * @tparam T * @param array * @return */
    int getsize(T &array) { 
    	return sizeof(array) / sizeof(array[0]);
    }
    
    
    int main() { 
    	// int a[] = {5, 1, 4, -1, -1, 3, 6};
    	// int a[] = {2,1,3};
    	int a[] = {  10, 5, 15, -1, -1, 6, 20 };
    	// 创建二叉树
    	TreeNode *pNode = create(a, getsize(a));
    	// preorder(pNode);
    	Solution *pSolution = new Solution;
    	bool b = pSolution->isValidBST(pNode);
    	cout << b << endl;
    
    	system("pause");
    	return 0;
    }

运行结果

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNTEwNTk3_size_16_color_FFFFFF_t_70]

有点菜，有时间再优化一下。

# 3、总结 #

书上的代码直接运行绝大部分是对的，但是总有一些软件的更新使得作者无能为力。之前的API是对的，但是之后就废弃了或修改了是常有的事。所以我们需要跟踪源代码。这只是一个小小的问题，如果没有前辈的无私奉献，很难想象我们自己一天能学到多少内容。感谢各位前辈的辛勤付出，让我们少走了很多的弯路！

点个赞再走呗！欢迎留言哦！

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNTEwNTk3_size_16_color_FFFFFF_t_70]: /images/20230312/03d23cb4591b4cd9a119cd8b378d99bb.png