java solution, convert Tree into a String, then using contains. O(n) time and O(1) space


  • 0

    Changing the tree "s" and "t" into Strings "ss" and "st" and then judge if "st" is the substring of "ss".
    tree 1,2,3 ---cinvert---> [1]1(l2 r3).
    the format is [length of root.val] + root.val + (leftchid, rightchild) .
    The algorithm itself is O(n) and "contains" cost O(n)
    hope it helps~

    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    public class Solution {
        public boolean isSubtree(TreeNode s, TreeNode t) {
            String s1 = convertTree(s);
            String s2 = convertTree(t);
            return s1.contains(s2);
        }
        
        protected String convertTree(TreeNode root) {
            if(root == null) {
                return "";
            }
            String s = "" + root.val;
            s = "[" + s.length() + "]" + s;
            String left = convertTree(root.left);
            String right = convertTree(root.right);
            if(left.length() != 0) {
                left = "l" + left;
            }
            if(right.length() != 0) {
                right = "r" + right;
            }
            return s + "(" + left + right + ")";
        }
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.