当前位置:首页 > 未命名 > 正文内容

【解题报告】lintcode245子树

u3blog9年前 (2016-05-13)未命名320

题意

给出两个树,求树二是否为树一的子树 判断是否为子树的条件是从某一结点切断,剩下的部分与树二相同 例子 QQ截图20160513105417 此时,t2是t1的子树

解法

首先,拿到t2的root,在t1中查找值相同的节点,存入数组,因为可能不止一个起点 然后再从这些节点出发,对比t2,来求是否为子树

代码

public class Solution {
         List<TreeNode> roots;
//求出发点
   public TreeNode findRoot(TreeNode node, TreeNode root) {
             if (node == null)
            return null;
        if (node.val == root.val){
            roots.add(node);
        }
             findRoot(node.left, root);
             findRoot(node.right, root);
        return null;
    }
//判断从起点开始是否相同
    public boolean findChildTree(TreeNode node,TreeNode root){
        if (node == null&&root == null)
            return true;
        if(node == null&&root != null)
            return false;
        if(node != null&&root == null)
            return false;
        if(node.val != root.val)
            return false;
        if(findChildTree(node.left,root.left)&&findChildTree(node.right,root.right))
            return true;
        else
            return false;
    }
    public boolean isSubtree(TreeNode T1, TreeNode T2) {
        // write your code here
        roots = new ArrayList<>();
        if (T2 == null)
            return true;
        TreeNode node = findRoot(T1,T2);
        for (int i = 0;i < roots.size();i++){
            if (findChildTree(roots.get(i),T2))
            {
                return true;
            }
        }
        return false;
    }

}   

扫描二维码推送至手机访问。

版权声明:本文由u3blog发布,如需转载请注明出处。

本文链接:https://u3blog.xyz/?id=385

分享给朋友:

发表评论

访客

◎欢迎参与讨论,请在这里发表您的看法和观点。