列表

详情

700. 二叉搜索树中的搜索

给定二叉搜索树（BST）的根节点 root 和一个整数值 val。

你需要在 BST 中找到节点值等于 val 的节点。 返回以该节点为根的子树。 如果节点不存在，则返回 null 。

 

示例 1:

输入：root = [4,2,7,1,3], val = 2
输出：[2,1,3]

示例 2:

输入：root = [4,2,7,1,3], val = 5
输出：[]

 

提示：

相似题目

最接近的二叉搜索树值

二叉搜索树中的插入操作

原站题解

去查看

上次编辑到这里，代码来自缓存 点击恢复默认模板
/** * 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) { } };

golang 解法, 执行用时: 20 ms, 内存消耗: 7.2 MB, 提交时间: 2021-07-26 13:59:09 

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func searchBST(root *TreeNode, val int) *TreeNode {
    if root == nil {
        return nil
    }
    if root.Val > val {
        return searchBST(root.Left, val)
    } else if root.Val < val {
        return searchBST(root.Right, val)
    } else {
        return root
    }
}

php 解法, 执行用时: 32 ms, 内存消耗: 17.2 MB, 提交时间: 2021-06-02 15:33:02 

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     public $val = null;
 *     public $left = null;
 *     public $right = null;
 *     function __construct($val = 0, $left = null, $right = null) {
 *         $this->val = $val;
 *         $this->left = $left;
 *         $this->right = $right;
 *     }
 * }
 */
class Solution {

    /**
     * @param TreeNode $root
     * @param Integer $val
     * @return TreeNode
     */
    function searchBST($root, $val) {
        while ( $root != null && $root->val != $val ) {
            $root = $root->val > $val ? $root->left : $root->right;
        }
        return $root;
    }
}

php 解法, 执行用时: 56 ms, 内存消耗: 17.3 MB, 提交时间: 2021-06-02 15:28:27 

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     public $val = null;
 *     public $left = null;
 *     public $right = null;
 *     function __construct($val = 0, $left = null, $right = null) {
 *         $this->val = $val;
 *         $this->left = $left;
 *         $this->right = $right;
 *     }
 * }
 */
class Solution {

    /**
     * @param TreeNode $root
     * @param Integer $val
     * @return TreeNode
     */
    function searchBST($root, $val) {
        $queue = [$root];
        while ( !empty($queue) ) {
            $node = array_shift($queue);
            if ( $node->val == $val ) return $node;
            if ( $node->right )
                $queue[] = $node->right;
            if ( $node->left )
                $queue[] = $node->left;
        }
        return null;
    }
}

上一题

© 2024 leetcode.cn