LeetCode 653. 兩數之和 IV - 輸入 BST(Two Sum IV - Input is a BST)

653. 兩數之和 IV - 輸入 BST

653. Two Sum IV - Input is a BST

題目描述

給定一個二叉搜尋樹和一個目标結果，如果 BST 中存在兩個元素且它們的和等于給定的目标結果，則傳回 true。

LeetCode653. Two Sum IV - Input is a BST簡單

案例 1:

輸入:

5
   / \
  3   6
 / \   \
2   4   7
           

Target = 9

輸出: True

案例 2:

輸入:

5
   / \
  3   6
 / \   \
2   4   7
           

Target = 28

輸出: False

Java 實作

TreeNode Class

public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }
}                

import java.util.ArrayList;
import java.util.List;

class Solution {
    public boolean findTarget(TreeNode root, int k) {
        if (root == null) {
            return false;
        }
        return BST(root, k, new ArrayList<>());
    }

    public boolean BST(TreeNode root, int k, List<Integer> list) {
        if (root == null) {
            return false;
        }
        if (list.contains(k - root.val)) {
            return true;
        }
        list.add(root.val);
        return BST(root.left, k, list) || BST(root.right, k, list);
    }
}                

相似題目

• 1. 兩數之和 Two Sum
• 167. 兩數之和 II - 輸入有序數組 Two Sum II - Input array is sorted
• 170. 兩數之和 III - 資料結構設計 Two Sum III - Data structure design

參考資料

• https://leetcode.com/problems/two-sum-iv-input-is-a-bst/
• https://leetcode-cn.com/problems/two-sum-iv-input-is-a-bst/

轉載于:https://www.cnblogs.com/hglibin/p/11012920.html