[LeetCode] 572. Subtree of Another Tree

轉自LeetCode

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.

<Solution>

和 100. Same Tree 類似，但變成是要找 subRoot tree，需要點變化

想法如下

• 這題直覺是要用遞迴解，因為過程中會需要返回上層再做一次檢查

• 歷遍 tree s，把每個 node 都當作 root，去和 t 比對，看看是否相等。不相等，就繼續遞迴找

code 如下

C++(參考答案)

	/**
	* Definition for a binary tree node.
	* struct TreeNode {
	* int val;
	* TreeNode *left;
	* TreeNode *right;
	* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
	* };
	*/
	class Solution {
	public:
	bool isSubtree(TreeNode* s, TreeNode* t) {
	return traverse(s, t);
	}
	bool traverse(TreeNode *s, TreeNode *t) {
	return s && (equal(s, t) || traverse(s->left, t) || traverse(s->right, t));
	}
	bool equal(TreeNode *sNode, TreeNode *tNode) {
	if(!sNode && !tNode) {
	return true;
	}
	else if(!sNode || !tNode) {
	return false;
	}
	return sNode->val == tNode->val && equal(sNode->left, tNode->left) && equal(sNode->right, tNode->right);
	}
	};

view raw subTreeOfAnotherTree.cpp hosted with ❤ by GitHub

Java

	/**
	* Definition for a binary tree node.
	* public class TreeNode {
	* int val;
	* TreeNode left;
	* TreeNode right;
	* TreeNode(int x) { val = x; }
	* }
	*/
	class Solution {
	public boolean isSubtree(TreeNode s, TreeNode t) {
	return traverse(s,t);
	}
	private boolean traverse(TreeNode s, TreeNode t) {
	return s != null && (equal(s,t) || traverse(s.left, t) || traverse(s.right,t));
	}
	private boolean equal(TreeNode sNode, TreeNode tNode) {
	if(sNode == null && tNode == null) {
	return true;
	}
	else if(sNode == null || tNode == null) {
	return false;
	}
	return sNode.val == tNode.val && equal(sNode.left, tNode.left) && equal(sNode.right, tNode.right);
	}
	}

view raw subTreeOfAnotherTree.java hosted with ❤ by GitHub

kotlin

	/**
	* Example:
	* var ti = TreeNode(5)
	* var v = ti.`val`
	* Definition for a binary tree node.
	* class TreeNode(var `val`: Int) {
	* var left: TreeNode? = null
	* var right: TreeNode? = null
	* }
	*/
	class Solution {
	fun isSubtree(root: TreeNode?, subRoot: TreeNode?): Boolean {
	return when {
	root == null -> false
	isSame(root, subRoot) -> true
	else -> isSubtree(root?.left, subRoot) || isSubtree(root?.right, subRoot)
	}
	}
	fun isSame(t: TreeNode?, s: TreeNode?): Boolean {
	return when {
	t == null && s == null -> true
	t == null || s == null -> false
	t!!.`val` != s!!.`val` -> false
	else -> isSame(t!!.left, s!!.left) && isSame(t!!.right, s!!.right)
	}
	}
	}

view raw subtree_of_another_tee.kt hosted with ❤ by GitHub