Open youngyangyang04 opened 5 months ago
class Solution {
private List<Integer> list = new ArrayList<>();
public boolean isValidBST(TreeNode root) {
inorderTraversal(root);
for (int i = 1; i < list.size(); i++) {
if (list.get(i) <= list.get(i - 1)) {
return false;
}
}
return true;
}
private void inorderTraversal(TreeNode node) {
if (node == null) return;
inorderTraversal(node.left);
list.add(node.val);
inorderTraversal(node.right);
}
}
C++最后一个递归方式 用c语言提交代码,定义一个全局变量指针pre通过不了力扣第47个样例( 只含一个根结点的二叉树)
可以维护两个状态hasLB
和hasUB
来储存上下界是否已经初始化, 这样就避免了只有一个根节点的时候要特殊讨论
bool isValidBST(TreeNode* root, int lb, int ub, bool hasLB, bool hasUB) {
if (root == NULL) {
return true;
}
bool result = true;
if (hasLB) {
result = result && (root -> val > lb);
}
if (hasUB) {
result = result && (root -> val < ub);
}
return result && isValidBST(root -> left, lb, root -> val, hasLB, true) && isValidBST(root -> right, root -> val, ub, true, hasUB);
}
bool isValidBST(TreeNode* root) {
return isValidBST(root, 0, 0, false, false);
}
这个定义pre指针的思路真的很巧妙,很多问题都可以通过这种思路来应对首节点(即遍历过程中的首个值)不好处理的问题
https://www.programmercarl.com/0098.%E9%AA%8C%E8%AF%81%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91.html