rustgym/leetcode/
_653_two_sum_4.rs

1struct Solution;
2use rustgym_util::*;
3use std::cmp::Ordering::*;
4
5trait Inorder {
6    fn inorder(&self, v: &mut Vec<i32>, target: i32);
7}
8
9impl Inorder for TreeLink {
10    fn inorder(&self, v: &mut Vec<i32>, target: i32) {
11        if let Some(node) = self {
12            let node = node.borrow();
13            let left = &node.left;
14            let right = &node.right;
15            Self::inorder(left, v, target);
16            v.push(node.val);
17            Self::inorder(right, v, target);
18        }
19    }
20}
21
22impl Solution {
23    fn find_target(root: TreeLink, k: i32) -> bool {
24        let mut v = vec![];
25        root.inorder(&mut v, k);
26        let n = v.len();
27        let mut l = 0;
28        let mut r = n - 1;
29        while l < r {
30            let sum = v[l] + v[r];
31            match sum.cmp(&k) {
32                Greater => {
33                    r -= 1;
34                }
35                Less => {
36                    l += 1;
37                }
38                Equal => {
39                    return true;
40                }
41            }
42        }
43        false
44    }
45}
46
47#[test]
48fn test() {
49    let root = tree!(5, tree!(3, tree!(2), tree!(4)), tree!(6, None, tree!(7)));
50    assert_eq!(Solution::find_target(root, 9), true);
51}
rustgym/leetcode/_653_two_sum_4.rs

rustgym/leetcode/
_653_two_sum_4.rs
