题解 | #树的子结构 回溯思想#

我的思路：
1、在递归之前临时将root2存一下（root3），等到子树判断不相等的时候root2就回溯到初始状态
2、is函数中的root4也是一个回溯的标志，如果val值相等就一直原封不动的传下去，当不相等的时候就把此标志作为下一个root1递归，达到递归回溯的效果~

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

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

    }

}
*/
public class Solution {
    //可供回溯的root2节点
    TreeNode root3 = new TreeNode(0);

    public boolean HasSubtree(TreeNode root1,TreeNode root2) {
        if(root2==null||root1==null){
            return false;
        }
        root3 = root2;
        return is(root1,root2,root1);
    }

    boolean is(TreeNode root1,TreeNode root2,TreeNode root4){
        if(root2==null){
            //这里是最重要的地方，当root2已经为null了，就代表前面的递归都是val相等，在这里就可以结束判断了.
            return true;
        }
        if(root1==null){
            return false;
        }
        //加快结束判断
        if(root1.val==root2.val
           &&root1.left==null
           &&root1.right==null
           &&root2.left==null
           &&root2.right==null
          ){
            return true;
        }
        if(root1.val==root2.val){
            return is(root1.left,root2.left,root4)&&is(root1.right,root2.right,root4);
        }else{
            //回溯到之前存储的root1节点处，避免遗漏答案，同时初始化root2
            return is(root4.left,root3,root4.left)||is(root4.right,root3,root4.right);
        }
    }
}

希望这个思维对你有所帮助！XD