Java Solution, tree traversal


  • 46

    For each node during pre-order traversal of s, use a recursive function isSame to validate if sub-tree started with this node is the same with t.

    public class Solution {
        public boolean isSubtree(TreeNode s, TreeNode t) {
            if (s == null) return false;
            if (isSame(s, t)) return true;
            return isSubtree(s.left, t) || isSubtree(s.right, t);
        }
        
        private boolean isSame(TreeNode s, TreeNode t) {
            if (s == null && t == null) return true;
            if (s == null || t == null) return false;
            
            if (s.val != t.val) return false;
            
            return isSame(s.left, t.left) && isSame(s.right, t.right);
        }
    }
    

  • 4
    Y

    Same idea. I use iterative way for isSubtree to save one extra method...

    public boolean isSubtree(TreeNode s, TreeNode t) {
        Queue<TreeNode> nodes = new ArrayDeque<>();
        nodes.offer(s);
        while (!nodes.isEmpty()) {
            TreeNode node = nodes.poll();
            if (isSameTree(node, t)) {
                return true;
            }
            if (node.left != null) {
                nodes.offer(node.left);
            }
            if (node.right != null) {
                nodes.offer(node.right);
            }
        }
        return false;
    }
    
    public boolean isSameTree(TreeNode s, TreeNode t) {
        if (s == null && t == null) {
            return true;
        }
        if (s == null || t == null) {
            return false;
        }
        if (s.val != t.val) {
            return false;
        } else {
            return isSameTree(s.left, t.left) && isSameTree(s.right, t.right);
        }
    }
    

  • 0

    clear and straightforward, nice solution!


  • 2

    @shawngao I think the isSame() can be modified like this

    private boolean isSame(TreeNode s, TreeNode t) {
            if(s==null||t==null)return s==t;
            if (s.val != t.val) return false;
            return isSame(s.left, t.left) && isSame(s.right, t.right);
        }
    }
    

  • 0
    S

    @shawngao Maybe there is no need to check if (s.val == t.val) in isSubtree since it will be checked in your isSame at the first attempt.

    C++ version:

    class Solution {
    public:
        bool isSubtree(TreeNode* s, TreeNode* t) {
            if (isIdentical(s, t))
                return true;
            return (s->left == nullptr ? false: isSubtree(s->left, t))
                || (s->right == nullptr ? false: isSubtree(s->right, t));
        }
        
        // whether two trees are identical (both structure and node values)
        bool isIdentical(const TreeNode* s, const TreeNode* t){
            if (s == nullptr && t == nullptr)
                return true;
            if ((s == nullptr && t != nullptr) || (s != nullptr && t == nullptr))
                return false;
            // both non nullptr
            if (s->val != t->val)
                return false;
            return isIdentical(s->left, t->left) && isIdentical(s->right, t->right);
            
        }
    };

  • 0

    @shuhua Yes, you are right. Modified my post, thanks!


  • 0
    R

    @shawngao

    Very clean implementation !


  • 0
    J

    @shawngao

    I have the same idea with you. But I am kind of worried if the solution efficient enough.
    Because isSame method takes O(n) time and O(n) space. So the time complexity should be O(n ^ 2).

    Is there any more efficient way so it could run in linear time?


  • 0
    L

    I think the first line of function isSame should be like this:
    if(s == t) return true; which means

    • A: s==null && t==null
    • B: s and t are the same node

  • 0

    Same idea.

    public class Solution {
        public boolean isSubtree(TreeNode s, TreeNode t) {
            if (isSameTree(s, t))   return true;
            if (s == null)  return false;
            return isSubtree(s.left, t) || isSubtree(s.right, t);
        }
        
        private boolean isSameTree(TreeNode s, TreeNode t) {
            if (s == null && t == null) return true;
            if (s == null || t == null) return false;
            
            return s.val == t.val && isSameTree(s.left, t.left) && isSameTree(s.right, t.right);
        }
    }
    

  • 0
    Z

    Similar C++ solution

    class Solution {
    public:
        bool isSubtree(TreeNode* s, TreeNode* t) {
            return isSametree(s, t) || (s != nullptr && (isSubtree(s -> left, t) || isSubtree(s -> right, t)));
        }
        
        bool isSametree(TreeNode *s, TreeNode *t) {
            if(s == nullptr && t == nullptr)  return true;
            if(s == nullptr || t == nullptr)  return false;
            return s -> val == t -> val && isSametree(s -> left, t -> left) && isSametree(s -> right, t -> right);
        }
    };
    

  • 0
    Y

    what if TreeNode t is null? Since an empty tree is always a subtree, we need to return true.

    '''
    public boolean isSubtree(TreeNode s, TreeNode t){
    if (t == null) return true;// the empty tree is always a subtree
    return subTree(s, t);
    }

    public boolean subTree(TreeNode r1, TreeNode r2){
        if (r1 == null){
            return false; //big tree empty
        } else if (matchTree(r1, r2)){
            return true;
        }
        return subTree(r1.left, r2)||subTree(r1.right, r2);
    
    }
    public boolean matchTree(TreeNode r1, TreeNode r2){
        if (r1 == null && r2 == null) return true;
        if (r1 == null || r2 == null) return false;
        if (r1.val != r2.val) return false; // data doesn't match
        return matchTree(r1.left, r2.left) && matchTree(r1.right, r2.right);
    }
    

    '''


  • 0
    V
    This post is deleted!

  • 0
    L

    Mine is the same

    public class Solution {
        public boolean isSubtree(TreeNode s, TreeNode t) {
            if(s == null && t !=null) return false; 
            return isSame(s, t) || isSubtree(s.left, t) || isSubtree(s.right, t);
        }
        public boolean isSame(TreeNode treeA, TreeNode treeB) {
            if (treeA == null && treeB == null) {
               return true; 
            } 
            else if (treeA == null || treeB == null) {
                return false;
            }
            return treeA.val == treeB.val && isSame(treeA.left, treeB.left) && isSame(treeA.right, treeB.right);
        }
    }
    
    

  • 0

    same:

    public boolean isSubtree(TreeNode s, TreeNode t) {
        if (s == null) return t == null; 
        return sameTree(s, t) || isSubtree(s.left, t) || isSubtree(s.right, t);
    }
    
    private boolean sameTree(TreeNode s, TreeNode t) {
        if (s == null && t == null) return true;
        if (s == null || t == null) return false;
        return s.val == t.val && sameTree(s.left, t.left) && sameTree(s.right, t.right);
    }

  • 0
    A

    @jz34 Looks good.
    But why my code is not accepted by OJ?

    The only one failed case is [1,2] [2], and expected result is false, my code returns true. But why? what [1,2] stands for?

    public class Solution {
    public boolean isSubtree(TreeNode s, TreeNode t) {

        String s1 = Serialize(s);
        String s2 = Serialize(t); 
        return s1.indexOf(s2) > -1; 
        
    }
    
    String Serialize(TreeNode root){
        if(root == null) return "null"; 
        return root.val + Serialize(root.left) + Serialize(root.right);
    }
    

    }


  • 0

    @Angaojxz
    [1,2]: "12nullnullnull"
    [2]: "2nullnull"
    [2] is inside [1,2] according to your algorithm


  • 0
    A

    @jz34

    Thanks,

    Following works

    public class Solution {
    public boolean isSubtree(TreeNode s, TreeNode t) {

        String s1 = Serialize(s);
        String s2 = Serialize(t); 
        return s1.indexOf(s2) > -1; 
        
    }
    
    String Serialize(TreeNode root){
        if(root == null) return "null"; 
        return "#" + root.val + Serialize(root.left) + Serialize(root.right);
    }
    

    }


  • 0
    W

    @shawngao Nice work, buddy! I am with the same idea with @shuhua ( does not need to check if (s.val == t.val) in the first line of isSubtree at first, but it is very interesting that the Java version without the check line cannot pass with the error " java.lang.NullPointerException" pointed to the line return isSubtree(s.left, t) || isSubtree(s.right, t) . However the C++ version @shuhua provided can pass. Wierd, I don't why, is it because if s.left (or s.right) is null then s.left (or s.right) cannot be passed as parameters? Hope anybody can explain, great thanks!


  • 0
    I

    @JansonLu
    The only "linear time" way I can imagine is to put all nodes into a pre/mid/postorder string and compare them, I remember some string compare method is linear time? We know that we need two strings (preorder + midorder for example)to describe a tree, thus the process could be described as below:

    1. ps = preorder s
    2. ms = midorder s
    3. pt = preorder t
    4. mt = midorder t
    5. return (pt is substr of ps) && (mt is substr of ms)
    

    The only problem is that, some substructure of s may have same preorder string with t, while other substructure of t may have same midorder string with t, in this circumstance the algorithm returns true but actually it's false. So I don't think this linear algorithm works for the problem.

    NOTE: To construct a faulty test case of this algorithm, you can find a tree u that has same preorder string with t, and another tree v that has same midorder string with t, and use them as the left & right child of any node to contruct s.


Log in to reply
 

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