LeetCode - Easy - 653. Two Sum IV - Input is a BST

左手的ㄟ右手 2022-10-22 07:38 2阅读 0赞

## Topic ##

*  Tree

## Description ##

[https://leetcode.com/problems/two-sum-iv-input-is-a-bst/][https_leetcode.com_problems_two-sum-iv-input-is-a-bst]

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

**Example 1:**  
![e7f53632dc9484122a593402cdf8b45e.png][]

Input: root = [5,3,6,2,4,null,7], k = 9
    Output: true

**Example 2:**

![c712503ed82899fadeb4fddd5069d88f.png][]

Input: root = [5,3,6,2,4,null,7], k = 28
    Output: false

**Example 3:**

Input: root = [2,1,3], k = 4
    Output: true

**Example 4:**

Input: root = [2,1,3], k = 1
    Output: false

**Example 5:**

Input: root = \[2,1,3\], k = 3  
Output: true

**Constraints:**

*  The number of nodes in the tree is in the range  \[ 1 , 1 0 4 \] \[1, 10^4\] \[1,104\].
 *   − 1 0 4 < = N o d e . v a l < = 1 0 4 -10^4 <= Node.val <= 10^4 −104<=Node.val<=104
 *  `root` is guaranteed to be a **valid** binary search tree.
 *   − 1 0 5 < = k < = 1 0 5 -10^5 <= k <= 10^5 −105<=k<=105

## Analysis ##

用两指针方法，一指针前序遍历，另一指针二分查找。

## Submission ##

public class TwoSumIVInputIsABST { 
    
    	public boolean findTarget(TreeNode root, int k) { 
    		return traverse(root, root, k);
    	}
    
    	// 前序遍历
    	private boolean traverse(TreeNode node, TreeNode root, int k) { 
    		if (node == null)
    			return false;
    
    		// node.val恰好是k的一半时，根据BST特性，没必要找另一个节点
    		if (2 * node.val != k && findTarget2(root, k - node.val))
    			return true;
    
    		return traverse(node.left, root, k) || traverse(node.right, root, k);
    	}
    
    	// 二分查找
    	private boolean findTarget2(TreeNode node, int targetValue) { 
    		if (node == null)
    			return false;
    
    		if (node.val == targetValue)
    			return true;
    
    		return findTarget2(targetValue < node.val ? node.left : node.right, targetValue);
    	}
    
    }

## Test ##

import static org.junit.Assert.*;
    import org.junit.Test;
    
    import com.lun.util.BinaryTree;
    import com.lun.util.BinaryTree.TreeNode;
    
    public class TwoSumIVInputIsABSTTest { 
    
    	@Test
    	public void test() { 
    		TwoSumIVInputIsABST obj = new TwoSumIVInputIsABST();
    
    		TreeNode root1 = BinaryTree.integers2BinaryTree(5, 3, 6, 2, 4, null, 7);
    		assertTrue(obj.findTarget(root1, 9));
    		assertFalse(obj.findTarget(root1, 28));
    
    		TreeNode root2 = BinaryTree.integers2BinaryTree(2, 1, 3);
    		assertTrue(obj.findTarget(root2, 4));
    		assertFalse(obj.findTarget(root2, 1));
    		assertTrue(obj.findTarget(root2, 3));
    	}
    }

[https_leetcode.com_problems_two-sum-iv-input-is-a-bst]: https://leetcode.com/problems/two-sum-iv-input-is-a-bst/
[e7f53632dc9484122a593402cdf8b45e.png]: /images/20221022/93094b4ba60a423aba4baf0f62cc3af1.png
[c712503ed82899fadeb4fddd5069d88f.png]: /images/20221022/0d9f605aa0c245cfb1f52602bf8cbf33.png