572. Subtree of Another Tree

发布时间：2020-12-14 04:18:40 所属栏目：大数据来源：网络整理

导读：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 b

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:

Given tree t:

   4
  /  1   2

Return?false.

//Approach1: recursive: 思路就是对于s树的每一个点和t进行isSameTree判断
//Time: O(n!),Space: O(h)
 
   public boolean isSubtree(TreeNode s,TreeNode t) {
        if (s == null) return false;//切勿忘记这一句，否则下面s.left和s.right就溢出
        
        if (isSameTree(s,t)) {
            return true;
        }
        
        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;
        }
        
        if (s.val == t.val) {
            return isSameTree(s.left,t.left) && isSameTree(s.right,t.right);
        }
        
        return false;
    }

//Approach2: traversal: 思路就是分别遍历s和t，看t是不是s的子集
//Time: O(n),Space: O(n)
    public boolean isSubtree(TreeNode s,TreeNode t) {
        StringBuilder s1 = serilize(s,new StringBuilder());
        StringBuilder t1 = serilize(t,new StringBuilder());
        return s1.toString().contains(t1.toString());
    }
    
    private StringBuilder serilize(TreeNode root,StringBuilder sb) {
        if (root == null) {
            sb.append(",#");//注意这里很重要，要先加，再加#，否则12和2就被判定为相同
            return sb;
        }
        
        sb.append("," + root.val);
        serilize(root.left,sb);
        serilize(root.right,sb);
        return sb;
    }

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!