SubtreeOfAnotherTree [source code]

public class SubtreeOfAnotherTree {
    public boolean isSubtree(TreeNode s, TreeNode t) {
        if (t == null && s == null) return true;
        else if (t == null || s == null) return false;
        else if (s.val == t.val) {
            if (equalTree(s.left, t.left) && equalTree(s.right, t.right)) return true;
        }
        return isSubtree(s.left, t) || isSubtree(s.right, t);
    }

    public boolean equalTree(TreeNode s, TreeNode t) {
        if (s == null && t == null) return true;
        else if (s == null || t == null) return false;
        else if (s.val != t.val) return false;
        else return equalTree(s.left, t.left) && equalTree(s.right, t.right);
    }

    public static void main(String[] args) {
        SubtreeOfAnotherTree tester = new SubtreeOfAnotherTree();
    }
}

看起来很简单的一个题目, 结果磨蹭了很久才做出来. 这个题目看起来很常规, 不过实际写代码的时候, 对于各种逻辑 branch 的处理要非常细心, 这个题目的 case 非常丰富, 变着花样的来 break 任何有一点漏洞的逻辑.

比如, 我一开始认为 s.val == t.val && isSubtree(s.left, t.left) && isSubtree(s.right, t.right) 应该是return true, 但是这个想法是有问题的, 而且立刻被一个 case break.

后面想到在 val 相等的情况下应该判断 equal, 但是 JAVA 内置的 equal 并不好使:

TreeNode s = new TreeNode(1);  
TreeNode t = new TreeNode(1);  
System.out.println(s.equals(t));//false  
System.out.println(s == t);//false

最后只能单独写一个 recursion 给 equality.

这个题目最后的代码虽然看起来很简单, 不过背后隐藏的问题很多, 什么时候该用 else, 什么时候不该用 else(直接 fallthrough), 都是在写代码的时候要认真考虑的选择.
一个重要的思考方式是, 在没一行的开始, 比如你现在这一行马上准备写一个 else, 提醒一下你这一行 implicit 的 condition(就是前面的几个 branch 全都 fail, 自然暗示你当前 branch 有一些现有的条件). remember where you currently are in the decision tree.

这个代码肯定是不完整的, 用了两个 recursion, 这个速度是不太好的, 最后的速度是: 29(55), 很 mediocre;

Problem Description

Given two non-empty binary trees s and t, check whether tree t has exactly the same structure and node values with a subtree of s. A subtree of s is a tree consists of a node in s and all of this node's descendants. The tree s could also be considered as a subtree of itself.

Example 1:
Given tree s:

 3  
/ \  

4 5
/ \
1 2
Given tree t:
4
/ \
1 2
Return true, because t has the same structure and node values with a subtree of s.
Example 2:
Given tree s:

 3  
/ \  

4 5
/ \
1 2
/
0
Given tree t:
4
/ \
1 2
Return false.
Difficulty:Easy
Category:Algorithms
Acceptance:41.02%
Contributor: xljob
Companies
facebook ebay
Related Topics
tree
Similar Questions
Count Univalue Subtrees Most Frequent Subtree Sum