题解 | 树的子结构

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 {

    public boolean HasSubtree(TreeNode root1,TreeNode root2) {
        if(root2==null) return false;
        ArrayList<TreeNode> r1=new ArrayList<>();
        ArrayList<TreeNode> r2=new ArrayList<>();
        r1=PreOrder(root1,r1);
        
        boolean flag=false;
        for(int i=0;i<r1.size();i++){
            flag=isSubTree(r1.get(i),root2);
            if(flag)
                return flag;
        }
        return false;
    }

    public ArrayList<TreeNode> PreOrder(TreeNode root,ArrayList<TreeNode> list){
        if(root==null) return list;
        list.add(root);
        if(root.left!=null)
           list = PreOrder(root.left,list);
        if(root.right!=null)
           list = PreOrder(root.right,list);
        return list;
    }

     

    public boolean isSubTree(TreeNode root1,TreeNode root2){
        if(root1==null&&root2==null) return true;
        if(root1!=null&&root2==null) return true;
        if(root1==null&&root2!=null) return false;
        if(root1.val!=root2.val) return false;
        return isSubTree(root1.left,root2.left)&&isSubTree(root1.right,root2.right);
    }
}

这个题目我使用的方法结合了集合框架和二叉树的知识。

概要： 我的这个方法可能看着不够巧妙，但是比较好理解。简单来说就是遍历树1里面的每一个节点，判断遍历到的节点作为根的子树是不是与树2相等。

具体步骤如下：

首先对树的根结点root1进行中序遍历，并存储在ArrayList中，这样的能够按照树的先序遍历将树里面的每一个节点存储下来。然后遍历ArrayList中的每一个节点r，判断以r为根的子树是不是与二叉树root2相同(这里对应的方法isSubTree)。在isSubTree里面，逻辑是这样的：1. 如果当前两个节点都是null,则返回true;

2. 如果当前节点root1不为空，而root2为空，则返回true;

3. 如果当前节点root1为null，root2不为null,则返回false;

4. 如果当前节点root1与root2都不为null，并且两个对应的值不等，则返回false;

5. 如果当前节点root1与root2都不为null,并且两个对应的值相等，则递归判断root1的左子树与root2的左子树，root1的右子树与root2的右子树，只有两个都返回true,最后情况5才返回5.