题目

leetcode:700

代码与解析

二叉搜索树,和普通二叉树不太一样,他是有序的树

  • 若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值;

  • 若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值

  • 它的左、右子树也分别为二又搜索树
    这就决定了,二又搜索树,递归遍历和送代遍历和普通二又树都不一样。

递归(二叉搜索树版)

这个并不需要辅助的递归函数,因为参数一致,而且不需要像遍历二叉树再向数组添加值那样要初始数组。

  • 确定参数及返回值
    参数要传入当前节点和val,要返回节点指针
    但是这个只要搜索到该节点就要立即返回,所以请见单层逻辑里遍历左节点前面加return

  • 确定终止条件
    如果当前节点等于nil返回nil, 或者当前节点等于val返回val,这两个都是返回自身

if root==nil||root.Val==val{
    return root
}
  • 单层逻辑
    一定要加return
if root.Val>val{
    return searchBST(root.Left, val)
}
if root.Val<val{
    return searchBST(root.Right, val)
}

全部代码

func searchBST(root *TreeNode, val int) *TreeNode {
    if root==nil||root.Val==val{
        return root
    }
    if root.Val>val{
        return searchBST(root.Left, val)
    }
    if root.Val<val{
        return searchBST(root.Right, val)
    }
    return nil
}

按普通二叉树遍历

https://blog.devilwst.top/2021/12/09/二叉树-种类与遍历/
这里说明一下,为什么这里要判断left,right是否为空,
因为和上面链接不一样,上面的没有返回值,return只是返回了告诉上一层改换路了,这个不一样, 这个直接返回一个nil,一个空的节点,不判断的话他会肆意递增

func searchBST(node *TreeNode, val int) *TreeNode {
    if node==nil{
        return nil
    }
    if node.Val==val{
        return node
    }

    left := searchBST(node.Left, val)
    right := searchBST(node.Right, val)
    //因为和上面链接不一样,上面的没有返回值,return只是返回了告诉上一层改换路了,这个不一样, 这个直接返回一个nil,一个空的节点,不判断的话他会肆意递增
    if left!=nil{
        return left
    }
    if right!=nil{
        return right
    }
    return nil
}

迭代

利用二叉搜索树性质

func searchBST(root *TreeNode, val int) *TreeNode {
    for root!=nil{
        if root.Val>val{
            root = root.Left
        }else if root.Val<val{
            root = root.Right
        }else{
            break
        }
    }
    return root

}

1 条评论

sfgh · 2021-12-20 23:20

nice 写的不错,正好在刷这道

发表评论

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用*标注

ICP备案号: 辽ICP备20003309号