[LeetCode] 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.

Thought process:
Traverse s. When I see a node whose value equals t.val, traverse both s and t and check if they match. If so, return true. Else, traverse s further.

Solution:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34

/** * 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) { if (s == null) { return t == null; } if (s.val == t.val && traverse(s, t)) { return true; } return isSubtree(s.left, t) || isSubtree(s.right, t); } private boolean traverse(TreeNode a, TreeNode t) { if (a == null && t == null) { return true; } if (a == null || t == null) { return false; } if (a.val != t.val) { return false; } return traverse(a.left, t.left) && traverse(a.right, t.right); } }

Time complexity:
Say s has s nodes and t has t nodes. The overall time complexity is O(st).