572. Is subtree

572_solution1.c

#include "tree_node.h"
#include <stdbool.h>

static bool isSameTree(struct TreeNode *r1, struct TreeNode *r2) {
  if (!r1 && !r2)
    return true;
  if (!r1 || !r2)
    return false;
  return r1->val == r2->val && isSameTree(r1->left, r2->left) &&
         isSameTree(r1->right, r2->right);
}

bool isSubtree(struct TreeNode *root, struct TreeNode *subRoot) {
  if (!subRoot)
    return true;
  if (!root)
    return false;
  return isSameTree(root, subRoot) || isSubtree(root->left, subRoot) ||
         isSubtree(root->right, subRoot);
}

tree_node.h

#pragma once

#include <stddef.h>

// Definition for a binary tree node.
struct TreeNode {
  int val;
  struct TreeNode *left;
  struct TreeNode *right;
};

572_solution1.cpp

#include "tree_node.h"

class Solution {
public:
  bool isSubtree(TreeNode *root, TreeNode *subRoot) {
    if (!subRoot)
      return true;
    if (!root)
      return false;
    return (isSameTree(root, subRoot) || isSubtree(root->left, subRoot) ||
            isSubtree(root->right, subRoot));
  }

  bool isSameTree(TreeNode *r1, TreeNode *r2) {
    if (!r1 && !r2)
      return true;
    if (!r1 || !r2)
      return false;
    return r1->val == r2->val && isSameTree(r1->left, r2->left) &&
           isSameTree(r1->right, r2->right);
  }
};

tree_node.h

#pragma once

// Definition for a binary tree node.
struct TreeNode {
  int val;
  TreeNode *left;
  TreeNode *right;
  TreeNode() : val(0), left(nullptr), right(nullptr) {}
  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  TreeNode(int x, TreeNode *left, TreeNode *right)
      : val(x), left(left), right(right) {}
};

572_solution1.go

package trees

func isSubtree(root *TreeNode, subRoot *TreeNode) bool {
    if subRoot == nil {
        return true
    }
    if root == nil {
        return false
    }
    return isSameTree(root, subRoot) || isSubtree(root.Left, subRoot) || isSubtree(root.Right, subRoot)
}

func isSameTree(r1 *TreeNode, r2 *TreeNode) bool {
    if r1 == nil && r2 == nil {
        return true
    }
    if r1 == nil || r2 == nil {
        return false
    }
    return r1.Val == r2.Val && isSameTree(r1.Left, r2.Left) && isSameTree(r1.Right, r2.Right)
}

tree_node.go

package trees

// Definition for a binary tree node.
type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

572_solution1.java

class Solution {
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        if (subRoot == null)
            return true;
        if (root == null)
            return false;
        return isSameTree(root, subRoot) || isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot);
    }

    private boolean isSameTree(TreeNode r1, TreeNode r2) {
        if (r1 == null && r2 == null)
            return true;
        if (r1 == null || r2 == null)
            return false;
        return r1.val == r2.val && isSameTree(r1.left, r2.left) && isSameTree(r1.right, r2.right);
    }
}

TreeNode.java

// Definition for a binary tree node.
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {}

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

572_solution1.js

const TreeNode = require("./tree_node");

var isSubtree = function (root, subRoot) {
  if (!subRoot) return true;
  if (!root) return false;
  return isSameTree(root, subRoot) || isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot);
};

function isSameTree(r1, r2) {
  if (!r1 && !r2) return true;
  if (!r1 || !r2) return false;
  return r1.val === r2.val && isSameTree(r1.left, r2.left) && isSameTree(r1.right, r2.right);
}

tree_node.js

// Definition for a binary tree node.
function TreeNode(val, left, right) {
  this.val = val === undefined ? 0 : val;
  this.left = left === undefined ? null : left;
  this.right = right === undefined ? null : right;
}

module.exports = TreeNode;

572_solution1.py

from typing import Optional

from tree_node import TreeNode


class Solution:
    def isSubtree(self, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:
        if not subRoot:
            return True
        if not root:
            return False
        return (
            self.isSameTree(root, subRoot)
            or self.isSubtree(root.left, subRoot)
            or self.isSubtree(root.right, subRoot)
        )

    def isSameTree(self, r1: Optional[TreeNode], r2: Optional[TreeNode]) -> bool:
        if not r1 and not r2:
            return True
        if not r1 or not r2:
            return False
        return (
            r1.val == r2.val
            and self.isSameTree(r1.left, r2.left)
            and self.isSameTree(r1.right, r2.right)
        )

tree_node.py

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

572_solution1.rs

use std::cell::RefCell;
use std::rc::Rc;

use crate::tree_node::TreeNode;

type Link = Option<Rc<RefCell<TreeNode>>>;

impl Solution {
    pub fn is_subtree(root: Link, sub_root: Link) -> bool {
        Self::contains(&root, &sub_root)
    }

    fn contains(root: &Link, sub_root: &Link) -> bool {
        if sub_root.is_none() {
            return true;
        }
        match root {
            None => false,
            Some(n) => {
                let n = n.borrow();
                Self::is_same_tree(root, sub_root)
                    || Self::contains(&n.left, sub_root)
                    || Self::contains(&n.right, sub_root)
            }
        }
    }

    fn is_same_tree(r1: &Link, r2: &Link) -> bool {
        match (r1, r2) {
            (None, None) => true,
            (Some(a), Some(b)) => {
                let (a, b) = (a.borrow(), b.borrow());
                a.val == b.val
                    && Self::is_same_tree(&a.left, &b.left)
                    && Self::is_same_tree(&a.right, &b.right)
            }
            _ => false,
        }
    }
}

tree_node.rs

use std::cell::RefCell;
use std::rc::Rc;

// 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,
        }
    }
}