Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

700. Search in a Binary Search Tree #216

Open
Tcdian opened this issue Jun 15, 2020 · 1 comment
Open

700. Search in a Binary Search Tree #216

Tcdian opened this issue Jun 15, 2020 · 1 comment
Labels

Comments

@Tcdian
Copy link
Owner

Tcdian commented Jun 15, 2020

700. Search in a Binary Search Tree

给定二叉搜索树(BST)的根节点和一个值。 你需要在BST中找到节点值等于给定值的节点。 返回以该节点为根的子树。 如果节点不存在,则返回 NULL。

Example

Given the tree:

        4
       / \
      2   7
     / \
    1   3

And the value to search: 2

You should return this subtree:

      2     
     / \   
    1   3

在上述示例中,如果要找的值是 5,但因为没有节点值为 5,我们应该返回 NULL。

@Tcdian Tcdian assigned Tcdian and unassigned Tcdian Jun 15, 2020
@Tcdian Tcdian added the Tree label Jun 15, 2020
@Tcdian
Copy link
Owner Author

Tcdian commented Jun 15, 2020

Solution

  • JavaScript Solution
/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} val
 * @return {TreeNode}
 */
var searchBST = function(root, val) {
    if (root === null) {
        return null;
    }
    if (root.val === val) {
        return root;
    } else if (root.val < val) {
        return searchBST(root.right, val);
    } else {
        return searchBST(root.left, val);
    }
};
  • TypeScript Solution
/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

function searchBST(root: TreeNode | null, val: number): TreeNode | null {
    if (root === null) {
        return null;
    }
    if (root.val === val) {
        return root;
    } else if (root.val < val) {
        return searchBST(root.right, val);
    } else {
        return searchBST(root.left, val);
    }
};

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
Projects
None yet
Development

No branches or pull requests

1 participant