树的子结构

树的子结构

给定两棵树，判断第二棵树是不是第一棵树的子树。

规定空树不是任意树的子结构。

想到用将树的结构转为先序，中序，或者后序序列，然后比较序列的包含关系，如果两颗树的同一个序列，比如先序序列，前树包含后树，那么返回true，否则返回false.

代码如下：

/**
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

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

    }

}
*/
import java.util.ArrayList;
public class Solution {
   public  void pre(TreeNode root,ArrayList<Integer> list) {
		 if(root==null) {
			 return;
		 }
		 list.add(root.val);
		 pre(root.left,list);
		 pre(root.right,list);
	 }
   public  boolean HasSubtree(TreeNode root1,TreeNode root2) {
    	
    	 if(root2==null) {
    		 return false;
    	 }
    	 
    	 if(root1==null) {
    		 return false;
    	 }
    	 
    	 ArrayList<Integer> list1=new ArrayList<Integer>();
    	 ArrayList<Integer> list2=new ArrayList<Integer>();
    	 
    	 pre(root1,list1);
    	 pre(root2,list2);
    	 
    	 return list1.containsAll(list2);
     }
    
}

不借用外部结构，只通过树的结点匹配与否来实现，递归版本如下：

public class Solution {
    public boolean HasSubtree(TreeNode root1,TreeNode root2) {
        if (root2 == null || root1 == null) {
            return false;
        }
        
        boolean res = false;
        if (root1.val == root2.val) {
            res = matchTree(root1, root2);
        }
        if (!res) {
            res = matchTree(root1.left, root2);
        }
        if (!res) {
            res = matchTree(root1.right, root2);
        }
        return res;
    }
    
    private boolean matchTree(TreeNode node1, TreeNode node2) {
        if (node2 == null) {
            return true;
        }
        if (node1 == null) {
            return false;
        }
        if (node1.val != node2.val) {
            return false;
        }
        return matchTree(node1.left, node2.left) && matchTree(node1.right, node2.right);
    }
}