700-98-530-501-701-669-538 Binary Search Tree

700 - Search in a Binary Search Tree

#easy
You are given the root of a binary search tree (BST) and an integer val.

Find the node in the BST that the node's value equals val and return the subtree rooted with that node. If such a node does not exist, return null.

Example 1:

Input: root = [4,2,7,1,3], val = 2
Output: [2,1,3]

Example 2:

Input: root = [4,2,7,1,3], val = 5
Output: []

/**
 * 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:
    TreeNode* searchBST(TreeNode* root, int val) {
        if ( root == NULL ) return NULL;
        TreeNode * result;
        if ( root -> val == val ) return root;
        else if ( root -> val > val ) result = searchBST( root -> left, val );
        else if ( root -> val < val ) result = searchBST( root -> right, val );
        return result;
    }
};

98 - Validate Binary Search Tree

#medium

Given the root of a binary tree, determine if it is a valid binary search tree (BST).

A valid 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.

Example 1:

Input: root = [2,1,3]
Output: true

Example 2:

Input: root = [5,1,4,null,null,3,6]
Output: false
Explanation: The root node's value is 5 but its right child's value is 4.

思路

我們要比較的是左子樹所有節點小於中間節點，右子樹所有節點大於中間節點。所以以上代碼的判斷邏輯是錯誤的。

例如： [10,5,15,null,null,6,20] 這個case：

二叉搜索樹

Solution 1 - 二元搜尋樹的中序排列(從小到大排列)。

bst的特性要想到中序(從小到大排列)。

class Solution {
private:
    vector<int> vec;
    void traversal(TreeNode* root) {
        if (root == NULL) return;
        traversal(root->left);
        vec.push_back(root->val); // 將二叉搜索樹轉換為有序數組
        traversal(root->right);
    }
public:
    bool isValidBST(TreeNode* root) {
        vec.clear(); // 不加這句在leetcode上也可以過，但最好加上
        traversal(root);
        for (int i = 1; i < vec.size(); i++) {
            // 注意要小於等於，搜索樹裡不能有相同元素
            if (vec[i] <= vec[i - 1]) return false;
        }
        return true;
    }
};

Solution 2 - 疊代法

/**
 * 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:
    void isValid( TreeNode * root, TreeNode * target_node, bool & is_valid ) {
        while ( root != NULL ) {
            if ( root == target_node ) return;
            else if ( root -> left == NULL && root -> right == NULL ) {
                is_valid = false;
                return;
            }
            else {
                if ( root -> val > target_node -> val ) root = root -> left;
                else if ( root -> val < target_node -> val ) root = root -> right;
                else {
                    is_valid = false;
                    return;
                }
            }
        }

        is_valid = false;
    }

    bool isValidBST(TreeNode* root) {
        queue<TreeNode*> que;
        que.push(root);
        bool is_valid = true;
        while ( !que.empty() ) {
            int que_size = que.size();
            for ( int i = 0; i < que_size; i++ ) {
                TreeNode * node = que.front();
                que.pop();   
                isValid( root, node, is_valid );
                if ( !is_valid ) return false;
                if ( node -> left ) que.push( node -> left );
                if ( node -> right ) que.push( node -> right );
            }

        }

        return true;
    }
};

Solution 3 - 最佳解 (省memory)

前一個節點 >= 當前節點 return false => root是不是每次都比pre大
(中序 -> 左節點，一層一層往後退的概念)

/**
 * 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:
    TreeNode* pre = NULL; // 用來記錄前一個節點
    bool isValidBST(TreeNode* root) {
        if (root == NULL) return true;
        bool left = isValidBST(root->left);

        if (pre != NULL && pre->val >= root->val) return false;
        pre = root; // key point: 記錄前一個節點

        bool right = isValidBST(root->right);
        return left && right;
    }
};