解法一：深度优先遍历

深度优先遍历+二叉搜索树性质剪枝。

  1. /**
  2.  * Definition for a binary tree node.
  3.  * public class TreeNode {
  4.  *     int val;
  5.  *     TreeNode left;
  6.  *     TreeNode right;
  7.  *     TreeNode(int x) { val = x; }
  8.  * }
  9.  */
  10. class Solution {
  11.     public TreeNode searchBST(TreeNode root, int val) {
  12.         if (root.val == val) {
  13.             return root;
  14.         }
  15.         TreeNode ans = null;
  16.         if ((root.left != null) && (val < root.val)) {
  17.             ans = searchBST(root.left, val);
  18.         }
  20.         if ((ans == null) && (root.right != null) && (val > root.val)) {
  21.             ans = searchBST(root.right, val);
  22.         }
  23.         return ans;
  24.     }
  25. }

解法二：广度优先搜索

广度优先搜索+二叉搜索树剪枝。

  1. /**
  2.  * Definition for a binary tree node.
  3.  * public class TreeNode {
  4.  *     int val;
  5.  *     TreeNode left;
  6.  *     TreeNode right;
  7.  *     TreeNode(int x) { val = x; }
  8.  * }
  9.  */
  10. class Solution {
  11.     public TreeNode searchBST(TreeNode root, int val) {
  12.         if (root == null) {
  13.             return null;
  14.         }
  15.         Queue<TreeNode> queue = new LinkedList<>();
  16.         queue.offer(root);
  17.         TreeNode ans = null;
  18.         while (!queue.isEmpty()) {
  19.             TreeNode temp = queue.poll();
  20.             if (temp.val == val) {
  21.                 ans = temp;
  22.                 break;
  23.             }
  24.             if ((val < temp.val) && (temp.left != null)) {
  25.                 queue.offer(temp.left);
  26.             }
  27.             if ((val > temp.val) && (temp.right != null)) {
  28.                 queue.offer(temp.right);
  29.             }
  30.         }
  31.         return ans;
  32.     }
  33. }