二叉搜索树中两个节点之和

题目描述

给定一个二叉搜索树的 根节点 root 和一个整数 k , 请判断该二叉搜索树中是否存在两个节点它们的值之和等于 k 。假设二叉搜索树中节点的值均唯一。参考leetcode

分析

1. 中序遍历二叉树，将节点的 value 保存到 ArrayList 中，ArrayList 中元素是有序的。
2. 采用双指针法，判断 ArrayList 中是否存在两个元素的和为 k。可参考：找出数组中两数之和为指定值的所有整数对

代码

/**
 * 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 boolean findTarget(TreeNode root, int k) {
        List<Integer> list = new ArrayList<>();

        //中序遍历二叉树
        inOrder(root, list);
        int i = 0;
        int j = list.size()-1;

        boolean exist = false;
        while(i < j){
            int sum = list.get(i) + list.get(j);
            if(sum > k){
                j--;
            }else if(sum < k){
                i++;
            }else{
                exist = true;
                break;
            }
        }
        return exist;
    }

    //中序遍历二叉树
    private void inOrder(TreeNode root, List<Integer> list){
        if(root == null){
            return;
        }
        inOrder(root.left, list);
        //将二叉树遍历的节点 val 保存到 list, 中序遍历得到有序的 list
        list.add(root.val);
        inOrder(root.right, list);
    }
}