算法：二叉查找树进阶

二叉查找树基础—Two Sum IV - Input is a BST

问题描述

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

Example 1:

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

Target = 9

Output: True

Java代码

class Solution {
    ArrayList<Integer> ints = null;
    public boolean findTarget(TreeNode root, int k) {
        ints = new ArrayList<>();
        preTraverse(root);
        
        int i =ints.size()-1;
        int j = 0;

    <strong>//在排序好的列表中找到两个和为目标值的序号
        while (j<i)
        {

            int sum = ints.get(i)+ints.get(j);
            if(sum==k)
                return true;
            if(sum<k)
                j++;
            else
                i--;
        }
        return false;
    }
</strong>　　//中序遍历，可以将二叉树从小到达排列出来！
    public void preTraverse(TreeNode T)
    {
        if(T!=null)
        {

            preTraverse(T.left);
            ints.add(T.val);
            preTraverse(T.right);
        }
    }
}

解题思考

我