이것은 leetcode weekly contest31의 두 번째 문제, easy 문제입니다.비교할 것은 자목이 아니라 자구조다.트리의 귀속 제목은 디버깅이 잘 되지 않습니다.
Editorial Solution에서 세 가지 접근 방식을 언급합니다: Approach #1 Check All Subtrees [Accepted] Approach #2 Using Preorder Traversal [Accepted] Approach #3 By Comparison of Nodes [Accepted]

approach 3

내가 당시에 쓴 것은 세 번째이다. 먼저 값이 같은 node를 찾은 다음에 이 두 node가 같은subtree를 대표하는지 비교한다.
Code:

    public boolean isSubtree(TreeNode s, TreeNode t) {
        //find node
        boolean res = false;
        if (s != null && t != null) {
            if (s.val == t.val) {
                res = checkSame(s, t);
            }
            if (!res) {
                res = isSubtree(s.left, t);
            }
            if (!res) {
                res = isSubtree(s.right, t);
            }
        }
        return res;
    }

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

이렇게 쓸 수도 있다.

    public boolean isSubtree(TreeNode s, TreeNode t) {
        return s != null && (checkSame(s, t) || isSubtree(s.left, t) || isSubtree(s.right, t));
    }

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

잘못된 시범

isSubtree의 부분은 여러 가지 묘사법이 있습니다. 위의 one-liner를 사용할 수 있지만 이렇게 쓰면 안 됩니다. 왜 그런지 알 수 있습니까?

    public boolean isSubtree(TreeNode s, TreeNode t) {
        if (s!=null){
            if (s.val == t.val) return checkSame(s , t );
            else return isSubtree(s.left , t) || isSubtree(s.right , t);
        }
        return false ;
//        return s != null && (checkSame(s, t) || isSubtree(s.left, t) || isSubtree(s.right, t));
    }

위의 코드는 주석된 1-liner에 비해 두 개의 같은 노드를 찾은 후에 s의 아이가 t의value와 같은지 판단하지 않았기 때문이다.s.val과 t.val과 뒤에 있는else는 관계가 아니라 관계이다.[1,1][1]의 테스트 케이스는 지나갈 수 없다.

하위 구조가 아니라 하위 구조인지 아닌지를 판단하려면

하위 트리가 아닌 하위 구조인지 판단하려면, checkSame는 다음과 같이 적습니다.

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

차례차례 돌아오니 정말 넓고 심오하다.

approach 1

모든 나무를 돌아다니며 set에 넣고 밑에 붙여주세요.

public class Solution {
    HashSet trees = new HashSet<>();
    public boolean isSubtree(TreeNode s, TreeNode t) {
        String tree = inorder(t);
        findAllSubTrees(s);
        return trees.contains(tree);
    }

    public String findAllSubTrees(TreeNode s) {
        if (s == null) {
            return "";
        }
        String val = findAllSubTrees(s.left) + s.val + findAllSubTrees(s.right);
        trees.add(val);
        return val;
    }

    public String inorder(TreeNode t) {
        if (t == null)
            return "";
        return inorder(t.left) + t.val + inorder(t.right);
    }
}

approach 2

traversal, indexOf로substring인지 아닌지 판단합니다.사실은inorder로도 가능하다는 것을 증명한다.

public class Solution {
    HashSet < String > trees = new HashSet < > ();
    public boolean isSubtree(TreeNode s, TreeNode t) {
        String tree1 = preorder(s, true);
        String tree2 = preorder(t, true);
        System.out.println(tree1);
        System.out.println(tree2);
        return tree1.indexOf(tree2) >= 0;
    }
    public String preorder(TreeNode t, boolean left) {
        if (t == null) {
            if (left)
                return "lnull";
            else
                return "rnull";
        }
        return "#"+t.val + " " +preorder(t.left, true)+" " +preorder(t.right, false);
    }
}