LeetCode刷题进阶之二叉树搜索树中的搜索 (700)
一、题目
演示示例：
二、测试代码
//方法一 递归/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */class Solution { public TreeNode searchBST(TreeNode root, int val) { if(root.val==val){ return root; }else if(val<root.val){ if(root.left==null){ return null; } return searchBST(root.left,val); }else{ if(root.right==null){ return null; } return searchBST(root.right,val); } }}//方法二 迭代/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */class Solution { public TreeNode searchBST(TreeNode root, int val) { while (root != null) { if (root.val == val) { return root; } else if (root.val > val) { root = root.left; } else { root = root.right; } } return null; }}三、运行情况
方法一：
方法二：
四、刷题总结
1、二叉搜索/查找/排序树（BST）的特性：
（1）若它的左子树不为空，则所有左子树上的值均小于其根节点的值；
（2）若它的右子树不为空，则所有右子树上的值均大于其根节点的值；
（3）它的左右子树分别为二叉搜索树。
2、本题的主要思路：
（1）若查找值等于当前结点值则直接返回；
（2）若查找值小于当前结点的值，根据二叉排序树的定义，我们需要向当前结点的左子树查找。若当前结点的左子树为空，则无法找到返回为空；若当前结点的左子树不为空，则递归向当前结点的左子树查找。
（3）若查找值大于等于当前结点的值，根据二叉排序树的定义，我们需要向当前结点的右子树查找。若当前结点的右子树为空，则无法找到返回为空；若当前结点的右子树不为空，则递归向当前结点的右子树查找。
3、递归与迭代的区别
递归：重复调用函数自身实现循环称为递归；
迭代：利用变量的原值推出新值称为迭代，或者说迭代是函数内某段代码实现循环。
赞 (0)