leetcode 653. Two Sum IV - Input is a BST

题目内容

Given a Binary Search Tree and a target number, return true if there exist two elements in the BST such that their sum is equal to the given target.

Example:
Input: 
    5
   / \
  3   6
 / \   \
2   4   7

Target = 9

Output: True

分析过程

  • 题目归类:
    树,遍历
  • 题目分析:
    此题给出的bst,所以考虑可以将bst转换成有序数组,然后在用2sum的方式进行求解。
  • 边界分析:
    • 空值分析
      tree == null
    • 循环边界分析
  • 方法分析:
    • 数据结构分析
      bst 可以用中序遍历获取有序的数组。
    • 状态机
    • 状态转移方程
    • 最优解
  • 测试用例构建

代码实现

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
import java.util.*;
class Solution {
    ArrayList<Integer> list = new ArrayList<>();
    public boolean findTarget(TreeNode root, int k) {
        if(root == null)
            return false;
        transfer(root);
        int i = 0;
        int j = list.size()-1;
        if(list.get(j)*2 < k)
            return false;
        if(list.get(i)*2 > k)
            return false;
        while(i<j){
            int sum = list.get(i)+list.get(j);
            if(sum==k)
                return true;
            else if(sum<k){
                i++;
            }else{
                j--;
            }
        }
        return false;
    }
    public void transfer(TreeNode root){
        if(root == null)
            return ;
        transfer(root.left);
        list.add(root.val);
        transfer(root.right);
    }
}
上一篇:开启和安装Kubernetes k8s 基于Docker For Windows


下一篇:关于二叉搜索树的一些总结