面试题26: 树的子树

剑指offer中原题是"树的子结构", 也就是只要子树B是树A的一部分就可以;
我实际做的这道题是leetcode上的, 他的要求是"树的子树", 也就是说要求子树B的树A严格意义上的子树, 区别很容易理解, 如下:

image.png

如果是"子结构",则判定为true
如果是"子树"的要求, 则判定为false
两段代码的区别已经放到了下面, 具体就是结束条件的不同
子结构:
树B为null, 说明树B已经匹配完毕, 返回true
树A为null, 说明前面的判断为树B非null, 也就是树B还没有匹配完, 树A就结束了, 返回false
两者都不为null 则判断是否相等, 不等返回false

只有以上全部通过, 才继续递归判断下一节点

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */

/**
遍历节点 如果s树的某个节点与t树的根节点匹配 则进入第二步

如果没有匹配 或者根节点匹配成功后, 子树匹配失败 继续遍历

*/


class Solution {
    public boolean isSubtree(TreeNode s, TreeNode t) {
        
        boolean result = false;
        if(s != null && t != null){
            if(s.val == t.val){
                result = isSubtreeCore(s, t);
            }
            if(result == false){ 
                //只有首节点匹配 且子树也匹配才会有result=true 其他情况都要继续遍历
                result = isSubtree(s.left, t);
            }
            if(result == false){
                result = isSubtree(s.right, t);
            }
        }
        return result;
    }
    
    
    public boolean isSubtreeCore(TreeNode s, TreeNode t){
        if(s == null && t == null) return true;
        //排除了都是null 只可能是一个为null 一个不为null
        if(s == null || t == null) return false;
        
        if(s.val != t.val) return false;
        
        //如果都有值且相等, 继续往下比较 判断
        return isSubtreeCore(s.left, t.left) && isSubtreeCore(s.right, t.right);
    }
}