题解 | #树的子结构#

import java.util.*;
/**     树的子结构
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;
    public TreeNode(int val) {
        this.val = val;
    }
}
*/
public class Solution {
    //判断以root1为根结点的树是否包含root2
    public boolean HasSubtree(TreeNode root1, TreeNode root2) {
        //空树不是任意一棵树的子结构，如果root1为空，包含了个寂寞
        if (root2 == null || root1 == null) {
            return false;
        }
        if (root2.val == root1.val
                && root2.left == null && root2.right == null) {
            return true;
        }
        boolean flag = false;
        //如果此结点值可以对上，继续判断后续是否可以对上，左右必须都满足，root2没有的分支就不用看了
        if (root1.val == root2.val) {
            if (root2.left != null && root2.right != null) {
                flag = HasSubtree(root1.left, root2.left) &&
                        HasSubtree(root1.right, root2.right);
            } else if (root2.left != null) {
                //子结构只有左子树，只用判断左边
                flag = HasSubtree(root1.left, root2.left);
            } else if (root2.right != null) {
                //子结构只有右子树，只用判断右边
                flag = HasSubtree(root1.right, root2.right);
            }
        }
        //当某一结点的flag为true，代表此结点是root2的根节点所在处
        //以roo1为根结点的树的每一个结点都需要遍历到，看是否包含root2
        flag = flag || HasSubtree(root1.left, root2) || HasSubtree(root1.right, root2);
        return flag;
    }
}