Leetcode|BST属性|98. 验证BST（每个节点需在区间中）

1 递归

【确定BST正确性必要条件】：需已知当前节点的父节点和祖父节点，才能准确固定区间

• 技巧1：将相邻3个节点的树指针作为参数传递，避免数据类型错误，比如节点值是long，但传入的是int
• 技巧2：使用左右两个父节点命名参数，若其中一个是父节点，则另一个必为祖父节点

代码语言：javascript复制

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool isValidBST(TreeNode* root, TreeNode* leftParent, TreeNode* rightParent) {
        /**
        leftParent: root的左父亲, leftParent->right == root
        rightParent: root的右父亲, rightParent->left == root
        **/
        if (!root) return true;
        if (leftParent && root->val <= leftParent->val) return false;
        if (rightParent && root->val >= rightParent->val) return false;
        // 这里传递了三个树节点{当前节点的左子节点, (左)父节点, 当前节点}}, 已知3个节点才能准确固定区间
        return isValidBST(root->left, leftParent, root) && isValidBST(root->right, root, rightParent);
    }
    bool isValidBST(TreeNode* root) {
        return isValidBST(root, nullptr, nullptr);
    }
};

2 迭代法（栈）

待二刷时再更啦~

int 递归 技巧 数据类型 指针

0 人点赞