美文网首页算法
LeetCode700.二叉搜索树中的搜索

LeetCode700.二叉搜索树中的搜索

作者: Timmy_zzh | 来源:发表于2021-09-18 16:08 被阅读0次
    1.题目描述
    • 给定二叉搜索树(BST)的根节点和一个值。 你需要在BST中找到节点值等于给定值的节点。 返回以该节点为根的子树。 如果节点不存在,则返回 NULL。
    例如,
    给定二叉搜索树:
    
            4
           / \
          2   7
         / \
        1   3
    和值: 2
    你应该返回如下子树:
          2     
         / \   
        1   3
    在上述示例中,如果要找的值是 5,但因为没有节点值为 5,我们应该返回 NULL。
    
    2.解题思路:
    • 2.1.递归法
      • 从根节点开始判断,如果根节点的值和目标值相等,则返回该节点
      • 如果目标值比根节点值小,说明目标值在在左子树中,否则在右子树中
      • 如果遍历到空节点,说明不存在该目标值
        public TreeNode searchBST(TreeNode root, int val) {
            if (root == null) {
                return null;
            }
            if (root.val == val) {
                return root;
            }
            if (val < root.val) {
                return searchBST(root.left, val);
            } else {
                return searchBST(root.right, val);
            }
        }
    
    
    • 2.2.迭代法
      • 新建一个node节点变量作为遍历节点,然后从根节点开始不断往下遍历
      • 找到与目标值相等的节点则返回,不想等则从左右子节点继续往下找
      • 直到节点不为null,否则返回null
        public TreeNode searchBST(TreeNode root, int val) {
            if (root == null) {
                return null;
            }
            while (root != null) {
                if (root.val == val) {
                    return root;
                }
                if (val < root.val) {
                    root = root.left;
                } else {
                    root = root.right;
                }
            }
            return null;
        }
    
    3.总结
    • 题解总结
      • 二叉搜索树bst,中序遍历会得到升序的数组,所以从二叉搜索树的根节点开始查找目标值时,
        • 可以根据bst的特性,目标值比根节点小,则目标值有可能在左子树中,从左子节点继续遍历
        • 如果比根节点值大,则从右子节点继续遍历
        • 相等的话直接返回根节点

    相关文章

      网友评论

        本文标题:LeetCode700.二叉搜索树中的搜索

        本文链接:https://www.haomeiwen.com/subject/ajhygltx.html