【LeetCode】 700. Search in a Binary Search Tree

Description

Given the root node of a binary search tree (BST) and a value. You need to find the node in the BST that the node's value equals the given value. Return the subtree rooted with that node. If such node doesn't exist, you should return NULL.
Note that an empty tree is represented by NULL, therefore you would see the expected output (serialized tree format) as [], not null.

給予一個BST的樹根和一個值。你需要找到BST中哪個節點的值和給予的值相等。回傳該節點為樹根的子樹。如果該節點不存在，你應該回傳NULL。
注意到一個空的樹應該用NULL表示，因此你會看到預期輸出(序列化輸出)是[]而非null。

Example:

Given the tree:
        4
       / \
      2   7
     / \
    1   3

And the value to search: 2
You should return this subtree:

      2     
     / \   
    1   3

Solution

• 雖然題目把資料結構的部分描寫得好像很複雜，但是LeetCode都已經幫我們建好樹結構了，因此我們只需要回傳指定節點即可。
• 遞迴結構，檢查自己：
  • 相等就回傳
  • 小於找左邊
  • 大於找右邊
• 可參考資結筆記。

Code

/**
 * 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 || root->val == val) return root;
        
        if(root->val < val) return searchBST(root->right, val);
        return searchBST(root->left, val);
    }
};

tags: LeetCode C++