JZ17_树的子结构.md

JZ17_树的子结构

两个递归，一个用于先确定A中哪个点作为子树的根去和B比较，第二个递归用于在确定根的值之后比较剩余子树中节点的值，我写了测试数据，和建树的方法，用于先序建立两棵树方便调试

public class Test {
    public static void main(String[] args) {
        //输入的是先序序列
        LinkedList<Character> list1 = new LinkedList<Character>();
        LinkedList<Character> list2 = new LinkedList<Character>();
        char[] ch1 = {'8', '8', '9', '#', '#', '2', '4', '#', '#', '7', '#', '#', '7', '#', '#'};
        char[] ch2 = {'8', '9', '#', '#', '2', '#', '#'};
        for (char c : ch1)
            list1.add(c);
        for (char c : ch2)
            list2.add(c);
        Solution solution = new Solution();
        //先序建立两棵树
        TreeNode root1 = solution.createTree(list1);
        TreeNode root2 = solution.createTree(list2);
        //测试遍历两棵树
//        solution.pre(root1);
//        System.out.println();
        boolean ans = solution.HasSubtree(root1, root2);
        System.out.println(ans);
    }
}

class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;
    }
}

class Solution {
    public void pre(TreeNode p) {
        if (p != null) {
            System.out.print(p.val);
            pre(p.left);
            pre(p.right);
        }
    }

    public TreeNode createTree(LinkedList<Character> list) {
        //遇到#除了返回null之外还需要右移一位
        if (list.getFirst() == '#') {
            list.removeFirst();
            return null;
        }
        char temp = list.removeFirst();
        TreeNode p = new TreeNode(temp - '0');
        p.left = createTree(list);
        p.right = createTree(list);
        return p;
    }

    public boolean HasSubtree(TreeNode root1,TreeNode root2) {
        //空树排除
        if (root1 == null || root2 == null) return false;
        return judgeRoot(root1, root2);
    }

    //首先递归遍历A树的每一个节点，判断以该节点为根节点的A的子树是否包含B整个树
    public boolean judgeRoot(TreeNode root1, TreeNode root2) {
        //只有A的非空节点才会被选择作为子书的根
        boolean ans = false;
        if (root1 != null) {
            //作为根，两个节点都不可能为空
            if (root1.val == root2.val) {
                ans = judgeSub(root1.left, root2.left) && judgeSub(root1.right, root2.right);
            }
            //若root1.val != root2.val或者即使root1.val == root2.val这部分也需要，因为依旧可能无法全部匹配
            //这里用||的短路逻辑处理，如果有true就不用继续算了，这句代码是核心
            ans = ans || judgeRoot(root1.left, root2) || judgeRoot(root1.right, root2);
        }
        return ans;
    }

    //在保证根节点的相同的情况下，递归遍历两棵树剩下的子书
    public boolean judgeSub(TreeNode root1, TreeNode root2) {
        //A没了，B还有，B就不可能是A的子树
        if (root1 == null && root2 != null) return false;
        //只要A树中包含B树即可，即使A的当前分支还能继续延伸
        if (root1 != null && root2 == null) return true;
        //表示这个分支两棵树形态是相同的
        if (root1 == null && root2 == null) return true;

        //处理非空节点
        if (root1.val != root2.val) return false;
        else {
            return judgeSub(root1.left, root2.left) && judgeSub(root1.right, root2.right);
        }
    }
}