LintCode 子树

题目

有两个不同大小的二进制树： T1 有上百万的节点； T2 有好几百的节点。请设计一种算法，判定 T2 是否为 T1的子树。

 注意事项

若 T1 中存在从节点 n 开始的子树与 T2 相同，我们称 T2 是 T1 的子树。
也就是说，如果在 T1 节点 n 处将树砍断，砍断的部分将与 T2 完全相同。

样例:
下面的例子中 T2 是 T1 的子树：

       1                3
      / \              / 
T1 = 2   3      T2 =  4
        /
       4
下面的例子中 T2 不是 T1 的子树：

       1               3
      / \               \
T1 = 2   3       T2 =    4
        /
       4

//Definition of TreeNode
public class TreeNode {
    public int val;
    public TreeNode left, right;

    public TreeNode(int val) {
        this.val = val;
        this.left = this.right = null;
    }
}

思路

采用递归思想，递归数每个节点，及其左右子树是否与子树相等。 先判断节点是否相等，找到相等的节点再判断左右子树。 判断相等的过程中，如果发现不等，直接结束，相等则继续。 判断是否是子树的过程中，先判断节点是否相等;节点不等，递归节点左子树;左子树不等，再递归右子树

代码

 public boolean isSubtree(TreeNode T1, TreeNode T2) {
        // write your code here
         boolean flag = false;
        if (T2 == null) return true;
        //判断节点是否相等
        flag = isSame(T1, T2);
        if (!flag) {
            //节点不等，递归节点左子树
            flag = isSubtree(T1.left, T2);
            if (!flag) {
                //左子树不等，递归右子树
                flag = isSubtree(T1.right, T2);
            }
        }
        return flag;
    }

    //判断两个树是否相同
    public boolean isSame(TreeNode a, TreeNode b) {
        //都为空，必定相同
        if (a == null && b == null) return true;
        //其中一个为空，必定不同
        if (a == null || b == null) return false;
        //节点值不等
        if (a.val != b.val) {
            return false;
        } else {
            //递归左子树
            boolean result = isSame(a.left, b.left);
            if (!result) {
                //发现不等，直接跳过
                return result;
            } else {
                //递归右子树
                return isSubtree(a.right, b.right);
            }
        }
    }