Leetcode刷题100天—700. 二叉搜索树中的搜索( 二叉树)—day34

太过爱你忘了你带给我的痛 2022-09-13 11:22 100阅读 0赞

前言：

> 作者：神的孩子在歌唱
> 
> 大家好，我叫运智

## 第一种解法 ##

![image-20210910141101626][]

## 第二种解法 ##

![image-20210910143740409][]

#### [700. 二叉搜索树中的搜索][700.] ####

难度简单152收藏分享切换为英文接收动态反馈

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

例如，

给定二叉搜索树:
    
            4
           / \
          2   7
         / \
        1   3
    
    和值: 2

你应该返回如下子树:

2     
         / \   
        1   3

在上述示例中，如果要找的值是 `5`，但因为没有节点值为 `5`，我们应该返回 `NULL`。

package 二叉树;
    
    import java.util.LinkedList;
    import java.util.Queue;
    
    import javax.xml.soap.Node;
    
    public class _700_二叉搜索树中的搜索 { 
    // 根据广度优先搜索遍历思想
        public TreeNode searchBST(TreeNode root, int val) { 
        	if (root==null) { 
    			return null;
    		}
    // 定义队列,后进先出
        	Queue<TreeNode> queue=new LinkedList<>();
    // 入队根节点
        	queue.add(root);
        	while(!queue.isEmpty()) { 
    // 出队
        		TreeNode node=queue.poll();
        		if (node.val==val) { 
    				return node;
    			}
        		if (node.left==null&&node.right==null) { 
    				continue;
    			}
        		if (node.left!=null) { 
        			queue.add(node.left);
    			}
        		if (node.right!=null) { 
    // 入队 
            		queue.add(node.right);
    			}
    
        		
        	}
        	return null;
        	
        }
    // 解法二 
        public TreeNode searchBST1(TreeNode root, int val) { 
            while (root != null && val != root.val)
                root = val < root.val ? root.left : root.right;
              return root;
        	
        }
    }

> 本人csdn博客：https://blog.csdn.net/weixin\_46654114
> 
> 转载说明：跟我说明，务必注明来源，附带本人博客连接。

[image-20210910141101626]: /images/20220828/2af223621db04b8194c7ce29066fffd4.png
[image-20210910143740409]: /images/20220828/29ae4ca73f104ea2b29150c5c030732b.png
[700.]: https://leetcode-cn.com/problems/search-in-a-binary-search-tree/