题目

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
}

按普通二叉树遍历

http://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

}