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:

    1.      3
    2.     / \
    3.    4   5
    4.   / \
    5.  1   2

    Given tree t:

    1.    4 
    2.   / \
    3.  1   2

    Return true, because t has the same structure and node values with a subtree of s.

    Example 2:
    Given tree s:

    1.      3
    2.     / \
    3.    4   5
    4.   / \
    5.  1   2
    6.     /
    7.    0

    Given tree t:

    1.    4
    2.   / \
    3.  1   2

    Return false.

    题意

    判断一个树t是否与另一个树s的子树相同。

    思路

    1. dfs处理。递归遍历s，对每个结点判断以该结点为根的子树是否与t相同。
    2. 官方解答中的另一种方法：对两树进行前序遍历，得到类似”#1lnullrnull”的字符串ss和tt，判断tt是否是ss的子串。

    代码实现 - dfs

    1. class Solution {
    2.     public boolean isSubtree(TreeNode s, TreeNode t) {
    3.         // t一定不为null
    4.         if (s == null) {
    5.             return false;
    6.         }
    7.         return judge(s, t) || isSubtree(s.left, t) || isSubtree(s.right, t);
    8.     }
    10.     private boolean judge(TreeNode s, TreeNode t) {
    11.         if (s == null && t == null) {
    12.             return true;
    13.         } else if (s == null || t == null || s.val != t.val) {
    14.             return false;
    15.         }
    16.         return judge(s.left, t.left) && judge(s.right, t.right);
    17.     }
    18. }

    代码处理 - 前序遍历

    1. class Solution {
    2.     public boolean isSubtree(TreeNode s, TreeNode t) {
    3.         String ss = preOrder(s, false);
    4.         String tt = preOrder(t, false);
    5.         return ss.indexOf(tt) != -1;
    6.     }
    8.     private String preOrder(TreeNode root, boolean isLeft) {
    9.         if (root == null) {
    10.             return isLeft ? "lnull" : "rnull";
    11.         }
    12.         return "#" + root.val + preOrder(root.left, true) + preOrder(root.right, false);
    13.     }
    14. }