BST 搜索：比较一次，丢掉一整边
左子树的值都比当前小，右子树都比当前大。target 只可能出现在其中一边，另一边连看都不用看。
从根出发：若 target 等于当前值返回该节点；小于则只查左子树；大于则只查右子树。BST 结构保证 target 只可能在一条分支上，所以每层比较都排除一半。递归或迭代均可。时间 O(h)，空间 O(h)（递归）/ O(1)（迭代）。
给定一棵二叉搜索树的根和一个整数 val，返回值等于 val 的那个节点；找不到返回 null。返回的是节点指针，不是布尔，也不是下标。
主例树 [4, 2, 7, 1, 3]，val = 5。根是 4，左挂 2（再挂 1、3），右挂 7。5 比 4 大、比 7 小，7 没有左孩子，答案是 null。演示路径 4→7，然后落空。
普通二叉树只能两边都搜。本文要回答：BST 多出来的那句「左边都小、右边都大」怎样把搜索收成一条折线，以及主例为什么在 7 的左侧停，而不去翻 2 那一侧。
缺口是方向，不是遍历整棵树
第一直觉前序扫一遍，碰上 5 就返回。主例没有 5，会把 4、2、1、3、7 都走完。结果能对，但左边那三棵与 5 无关：BST 保证它们全小于 4，而 5 已经大于 4。缺的不是「节点在不在」，而是比较一次之后，哪一边可以整棵丢掉。
当前节点 n 把树切成三块：n 自己、左子树、右子树。val == n.Val，命中，返回 n。val < n.Val，val 不可能出现在右子树，只走左。val > n.Val，只走右。走到 nil 仍没命中，返回 null。每一步排除一整边，路径长度就是树高。
用手走主例。从 4 起，5>4，丢掉左面的 2、1、3，只走右，演示第一帧 path=[4]。来到 7，5<7，丢掉 7 的右（本来也是空的），走左。7 的左是 nil，演示第二帧 path=[4,7] 之后没有下一跳。第三帧返回 null。
若 target 是 2：4 处 2<4 走左，2 处相等，返回那个节点，右面的 7 连看都不看。若 target 是 4，第一步就返回根。单节点树要么命中根要么 null。退化成一条链时 h=n，最坏仍可能扫 n 个点，平均平衡时是 O(log n)。
迭代和递归是同一条折线。迭代用一个指针往左或往右挪，空间 O(1)；递归把「当前根」换成左孩子或右孩子。不要写成左右都递归再拼结果——那就退回普通树搜索，BST 的性质浪费了。
只走一边一次比较排除一整棵子树。主例 5>4 之后，1、2、3 再也不会被访问。普通二叉树没有这句话，LC236 那种题必须两边都问。
Go：迭代搜索
func searchBST(root *TreeNode, val int) *TreeNode {for root != nil {if root.Val == val { return root }if val < root.Val { root = root.Left } else { root = root.Right }}return nil}
1指针还在就继续比。主例第一轮 5≠4 且 5>4，root 改成 7。
2相等立刻返回当前节点，不要再往下走。
3循环走穿说明这条折线上没有 val。主例 7 的左是 nil，返回 nil。
总结
比大小只走一边。主例 5：4 右、7 左，落空。
- BST 保证另一边不可能有 target。两边都搜是普通树，不是这题。
- 迭代与递归同一条路径；迭代省栈。
- 最坏退化链 O(n)，平衡时 O(log n)。