LeetCode88|两数之和IV-输入BST

1,问题简述

 

给定一个二叉搜索树和一个目标结果，如果 BST 中存在两个元素且它们的和等于给定的目标结果，则返回 true。

2，示例

案例 1: 输入: 5 / \ 3 6 / \ \ 2 4 7 Target = 9 输出: True   案例 2: 输入: 5 / \ 3 6 / \ \ 2 4 7 Target = 28 输出: False

3，题解思路

基于二叉树的中序遍历和双指针的思路进行求解

4，题解程序

import java.util.ArrayList; import java.util.List; public class FindTargetTest { private static List<Integer> list = new ArrayList<>(); public static void main(String[] args) { TreeNode t1 = new TreeNode(5); TreeNode t2 = new TreeNode(3); TreeNode t3 = new TreeNode(6); TreeNode t4 = new TreeNode(2); TreeNode t5 = new TreeNode(4); TreeNode t6 = new TreeNode(7); t1.left = t2; t1.right = t3; t2.left = t4; t2.right = t5; t3.right = t6; int k = 9; boolean target = findTarget(t1, k); System.out.println("target = " + target); } public static boolean findTarget(TreeNode root, int k) { if (root == null) { return false; } inOrder(root); int i = 0; int j = list.size() - 1; while (i < j) { Integer left = list.get(i); Integer right = list.get(j); if (left + right == k) { return true; } else if (left + right > k) { j--; } else { i++; } } return false; } private static void inOrder(TreeNode root) { if (root == null) { return; } if (root.left != null) { inOrder(root.left); } list.add(root.val); if (root.right != null) { inOrder(root.right); } } }

5，题解程序图片版

6,总结

目前自己输出的内容是第88道，我的计划是暂时输出100道题解，这就是自己暂时的计划吧，对于我自己来说也是比较有意义的一步，有时候在想，慢慢输出，才是自己独特的地方