572. Subtree of Another Tree

Given two non-empty binary trees s and t, check whether tree t has exactly the same structure and node values with a subtree of s. A subtree of s is a tree consists of a node in s and all of this node's descendants. The tree s could also be considered as a subtree of itself.

Example 1:
Given tree s:

     3
    / \
   4   5
  / \
 1   2
Given tree t:
   4 
  / \
 1   2
Return true, because t has the same structure and node values with a subtree of s.

 

Example 2:
Given tree s:

     3
    / \
   4   5
  / \
 1   2
    /
   0
Given tree t:
   4
  / \
 1   2
Return false.

 

Rust Solution

struct Solution;
use rustgym_util::*;

trait SubTree {
    fn is_subtree(&self, t: &TreeLink) -> bool;
}
impl SubTree for TreeLink {
    fn is_subtree(&self, t: &TreeLink) -> bool {
        if self == t {
            return true;
        }
        if let Some(node) = self {
            let left = &node.borrow().left;
            let right = &node.borrow().right;
            return left.is_subtree(t) || right.is_subtree(t);
        }
        false
    }
}

impl Solution {
    fn is_subtree(s: TreeLink, t: TreeLink) -> bool {
        s.is_subtree(&t)
    }
}

#[test]
fn test() {
    let s = tree!(3, tree!(4, tree!(1), tree!(2)), tree!(5));
    let t = tree!(4, tree!(1), tree!(2));
    assert_eq!(Solution::is_subtree(s, t), true);
}

Having problems with this solution? Click here to submit an issue on github.