这是悦乐书的第 280 次更新, 第 296 篇原创
01 看题和准备
今天介绍的是 LeetCode 算法题中 Easy 级别的第 148 题 (顺位题号是 653). 给定二进制搜索树和目标数, 如果 BST 中存在两个元素, 使得它们的总和等于给定目标, 则返回 true. 例如:
- 5
- / \
- 3 6
- / \ \
- 2 4 7
目标值: 9
输出: true
- 5
- / \
- 3 6
- / \ \
- 2 4 7
目标值: 28
输出: false
本次解题使用的开发工具是 eclipse,jdk 使用的版本是 1.8, 环境是 win7 64 位系统, 使用 Java 语言编写和测试.
02 第一种解法
判断在给出的一组数据中, 是否存在两个数之和等于给出的目标值, 只是给出的数据是个二叉搜索树. 所以, 我们需要先将数据抽出来, 遍历二叉树的节点值, 然后再去其中找那可能存在的两个数.
- /**
- * Definition for a binary tree node.
- * public class TreeNode {
- * int val;
- * TreeNode left;
- * TreeNode right;
- * TreeNode(int x) { val = x; }
- * }
- */
- class Solution {
- public boolean findTarget(TreeNode root, int k) {
- Map<Integer, Integer> map = new HashMap<Integer,Integer>();
- preOrder(root, map);
- // 遍历 map
- for (Integer key : map.keySet()) {
- // 分两种情况: k 由两个相同的节点值之和组成; 由不同的节点值之和组成
- if ((k-key == key && map.get(key)>= 2) || (k-key != key && map.containsKey(k-key))) {
- return true;
- }
- }
- return false;
- }
- // 使用递归, 前序遍历, 将二叉树的节点值添加进 map 中
- public void preOrder(TreeNode node, Map<Integer, Integer> map) {
- if (node == null) {
- return ;
- }
- map.put(node.val, map.getOrDefault(node.val, 0)+1);
- preOrder(node.left, map);
- preOrder(node.right, map);
- }
- }
03 第二种解法
我们也可以不使用 HashMap, 直接使用数组, 另外, 题目还说了此二叉树是个 BST, 那么它的中序遍历的节点值是有序的, 那么我们可以直接使用双指针而不必排序, 对所有的节点值直接判断.
- /**
- * Definition for a binary tree node.
- * public class TreeNode {
- * int val;
- * TreeNode left;
- * TreeNode right;
- * TreeNode(int x) { val = x; }
- * }
- */
- class Solution {
- public boolean findTarget(TreeNode root, int k) {
- List<Integer> list = new ArrayList<Integer>();
- inOrder(root, list);
- // 使用双指针
- int start = 0, end = list.size()-1;
- while (start <end) {
- int sum = list.get(start) + list.get(end);
- if (sum == k) {
- return true;
- }
- if (sum> k) {
- end--;
- } else {
- start++;
- }
- }
- return false;
- }
- // 使用递归, 中序遍历, 将二叉树的节点值添加进 list 中
- public void inOrder(TreeNode node, List<Integer> list) {
- if (node == null) {
- return ;
- }
- // 左子树
- inOrder(node.left, list);
- // 根节点
- list.add(node.val);
- // 右子树
- inOrder(node.right, list);
- }
- }
04 第三种解法
我们也可以使用 HashSet, 思路和第一种解法类似, 依旧使用递归遍历 BST 的节点, 但是此解法是直接在递归方法里面做了判断, 如果里面存在两个节点值的话, 就直接返回 true.
- /**
- * Definition for a binary tree node.
- * public class TreeNode {
- * int val;
- * TreeNode left;
- * TreeNode right;
- * TreeNode(int x) { val = x; }
- * }
- */
- class Solution {
- public boolean findTarget(TreeNode root, int k) {
- Set<Integer> set = new HashSet<Integer>();
- return helper(root, set, k);
- }
- // 使用递归, 将二叉树的节点值添加进 set 中
- public boolean helper(TreeNode node, Set<Integer> set, int k) {
- if (node == null) {
- return false;
- }
- if (set.contains(k-node.val)) {
- return true;
- }
- set.add(node.val);
- return helper(node.left, set, k) || helper(node.right, set, k);
- }
- }
05 第四种解法
针对上面的第三种解法, 我们可以使用迭代的方式来实现, 借助队列来实现.
- /**
- * Definition for a binary tree node.
- * public class TreeNode {
- * int val;
- * TreeNode left;
- * TreeNode right;
- * TreeNode(int x) { val = x; }
- * }
- */
- class Solution {
- public boolean findTarget(TreeNode root, int k) {
- Set<Integer> set = new HashSet<Integer>();
- Queue<TreeNode> queue = new LinkedList<TreeNode>();
- queue.offer(root);
- while (!queue.isEmpty()) {
- TreeNode node = queue.poll();
- // 判断是否包含另外一个数字
- if (set.contains(k-node.val)) {
- return true;
- }
- set.add(node.val);
- // 将其左右子节点继续入队列
- if (node.left != null) {
- queue.offer(node.left);
- }
- if (node.right != null) {
- queue.offer(node.right);
- }
- }
- return false;
- }
- }
06 小结
算法专题目前已日更超过四个月, 算法题文章 148 + 篇, 公众号对话框回复 [数据结构与算法] ,[算法] ,[数据结构] 中的任一关键词, 获取系列文章合集.
以上就是全部内容, 如果大家有什么好的解法思路, 建议或者其他问题, 可以下方留言交流, 点赞, 留言, 转发就是对我最大的回报和支持!
来源: http://www.jianshu.com/p/634b2f99e44e