41 lines
1.2 KiB
Rust
41 lines
1.2 KiB
Rust
// Definition for a binary tree node.
|
|
// #[derive(Debug, PartialEq, Eq)]
|
|
// pub struct TreeNode {
|
|
// pub val: i32,
|
|
// pub left: Option<Rc<RefCell<TreeNode>>>,
|
|
// pub right: Option<Rc<RefCell<TreeNode>>>,
|
|
// }
|
|
//
|
|
// impl TreeNode {
|
|
// #[inline]
|
|
// pub fn new(val: i32) -> Self {
|
|
// TreeNode {
|
|
// val,
|
|
// left: None,
|
|
// right: None
|
|
// }
|
|
// }
|
|
// }
|
|
use std::rc::Rc;
|
|
use std::cell::RefCell;
|
|
type Node = Option<Rc<RefCell<TreeNode>>>;
|
|
impl Solution {
|
|
pub fn has_path_sum(root: Node, target_sum: i32) -> bool {
|
|
match root {
|
|
None => false,
|
|
Some(node) => {
|
|
let mut node = node.borrow_mut();
|
|
let new_target = target_sum - node.val;
|
|
|
|
match (node.left.take(), node.right.take()) {
|
|
(None, None) => new_target == 0,
|
|
(Some(child), None) | (None, Some(child)) => Self::has_path_sum(Some(child), new_target),
|
|
(Some(left), Some(right)) => {
|
|
Self::has_path_sum(Some(left), new_target) ||
|
|
Self::has_path_sum(Some(right), new_target)
|
|
}
|
|
}
|
|
}
|
|
}
|
|
}
|
|
} |