Java 求解二叉搜索树中的搜索

梦里梦外; 2022-10-17 01:50 189阅读 0赞

### 文章目录 ###

*   *  一、题目
     *  二、题解
     *  三、递归法
     *  四、迭代法
     *  五、总结

## 一、题目 ##

给定二叉搜索树（BST）的根节点和一个值。 你需要在BST中找到节点值等于给定值的节点。 返回以该节点为根的子树。 如果节点不存在，则返回 NULL。

![在这里插入图片描述][20210601093845262.png]

## 二、题解 ##

该题可以利用二叉搜索树的特性去解决：

> 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；  
> 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；  
> 它的左、右子树也分别为二叉搜索树

## 三、递归法 ##

class Solution { 
        public TreeNode searchBST(TreeNode root, int val) { 
            //递归终止条件
            if (root == null || root.val == val) { 
                return root;
            }
            //递归逻辑
            return root.val > val ? searchBST(root.left, val) : searchBST(root.right, val);
        }
    }

## 四、迭代法 ##

常规的迭代法，是利用栈来模拟深度遍历，利用队列来模拟广度遍历

但是对于二叉搜索树，节点有序，所以可以不使用辅助栈或者队列就可以写出跌打法

一般二叉树，递归中包含着回溯的思想，比如一个左方向的分支走到头，需要掉头，走右分支

但是对于二叉搜索树，不需要回溯的过程，因为节点的有序性帮我们确定了搜索方向

class Solution { 
        public TreeNode searchBST(TreeNode root, int val) { 
            while (root != null && root.val != val) { 
                if (root.val > val) { 
                    root = root.left;
                } else { 
                    root = root.right;
                }
            }
            return root;
        }
    }

## 五、总结 ##

**二叉搜索树的特性：**

[20210601093845262.png]: /images/20221014/b3856e941a2a48959982e219c74e0ed3.png